题目描述

若l是一个奇数，那么l个数的数列的中位数就是数列中第 $\dfrac{l+1}{2}$ 大的数。

输入N个整数，$X$$_{1}$, $X$$_{2}$, ..., $X$$_{N}$ ，保证N为偶数。对于每一个i=1,2, ..., N，输出去掉xi之后数列的中位数$B$$_{i}$。

输入格式

两行，第一行为N，第二行为 $X$$_{1}$, $X$$_{2}$, ..., $X$$_{N}$ 。

输出格式

N行，第i行表示$B$$_{i}$。

说明/提示

• 2 $\le$ N $\le$ 200000
• N为偶数
• 1 $\le$ $X$$_{i}$ $\le$ 10$^{9}$

样例 1

输入

4
2 4 4 3

输出

4
3
3
4

样例 2

输入

2
1 2

输出

2
1

样例 3

输入

6
5 5 4 4 3 3

输出

4
4
4
4
4
4