Description

公司有N个人，其中会有若干个间谍。现在李华截取到了敌人内部的信息，它可以据此来推断出谁是间谍。

已知截取到的信息每个人都有一个号码Ai，其中对于所有1≤ K≤ (N+1)/2,A1,A1~A3,A1~A5……A1~A2*k-1,的中位数是间谍，现在请你给出所有间谍的号码。

Input Format

第一行为一个整数N，为公司人数

第二行给出N个数，截取信息中每个人的号码Ai

N≤100000

Output Format

共N行，每行为间谍号码，即数列A1~A2*k-1的中位数

7
1 3 5 7 9 11 6​

1
3
5
6​