Home

Problem Statement

When $l$ is an odd number, the median of $l$ numbers $a_1, a_2, ..., a_l$ is the $(\frac{l+1}{2})$-th largest value among $a_1, a_2, ..., a_l$.

You are given $N$ numbers $X_1, X_2, ..., X_N$, where $N$ is an even number. For each $i = 1, 2, ..., N$, let the median of $X_1, X_2, ..., X_N$ excluding $X_i$, that is, the median of $X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N$ be $B_i$.

Find $B_i$ for each $i = 1, 2, ..., N$.

Constraints

• $2 \leq N \leq 200000$
• $N$ is even.
• $1 \leq X_i \leq 10^9$
• All values in input are integers.

Sample Input 1

4
2 4 4 3

Sample Output 1

4
3
3
4

• Since the median of $X_2, X_3, X_4$ is $4$, $B_1 = 4$.
• Since the median of $X_1, X_3, X_4$ is $3$, $B_2 = 3$.
• Since the median of $X_1, X_2, X_4$ is $3$, $B_3 = 3$.
• Since the median of $X_1, X_2, X_3$ is $4$, $B_4 = 4$.

Sample Input 2

2
1 2

Sample Output 2

2
1

Sample Input 3

6
5 5 4 4 3 3

Sample Output 3

4
4
4
4
4
4