200950: [AtCoder]ARC095 C - Many Medians

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $300$ points

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.

Input

Input is given from Standard Input in the following format:

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

Output

Print $N$ lines. The $i$-th line should contain $B_i$.

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

Input

题意翻译

###### 题目描述 若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}$

Source/Category

加入题单

算法标签：