题目描述

当 $l$ 是一个奇数时，$l$ 个数 $a_1, a_2, ..., a_l$ 的中位数是 $a_1, a_2, ..., a_l$ 中第 $(\frac{l+1}{2})$ 大的值。

给定 $N$ 个数 $X_1, X_2, ..., X_N$，其中 $N$ 是一个偶数。对于每个 $i = 1, 2, ..., N$，设 $X_1, X_2, ..., X_N$ 去掉 $X_i$ 后的中位数为 $B_i$，即 $X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N$ 的中位数为 $B_i$。

找出对于每个 $i = 1, 2, ..., N$，$B_i$ 的值。

约束条件

• $2 \leq N \leq 200000$
• $N$ 是一个偶数。
• $1 \leq X_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入格式如下：

$N$ $X_1$ $X_2$ ... $X_N$

输出

打印 $N$ 行。第 $i$ 行应包含 $B_i$。

示例输入1

4
2 4 4 3

示例输出1

4
3
3
4

• 由于 $X_2, X_3, X_4$ 的中位数是 $4$，所以 $B_1 = 4$。
• 由于 $X_1, X_3, X_4$ 的中位数是 $3$，所以 $B_2 = 3$。
• 由于 $X_1, X_2, X_4$ 的中位数是 $3$，所以 $B_3 = 3$。
• 由于 $X_1, X_2, X_3$ 的中位数是 $4$，所以 $B_4 = 4$。

示例输入2

2
1 2

示例输出2

2
1

示例输入3

6
5 5 4 4 3 3

示例输出3

4
4
4
4
4
4