#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Many Medians

### Problem Statement

When `l` is an odd number, the median of `l` numbers `a _{1}, a_{2}, ..., a_{l}` is the

`(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`excluding

_{1}, X_{2}, ..., X_{N}`X`, that is, the median of

_{i}`X`be

_{1}, X_{2}, ..., X_{i-1}, X_{i+1}, ..., X_{N}`B`.

_{i}Find `B _{i}` for each

`i = 1, 2, ..., N`.

### Constraints

`2 ≤ N ≤ 200000``N`is even.`1 ≤ X`_{i}≤ 10^{9}- All values in input are integers.

### Input

Input is given from Standard Input in the following format:

NX_{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`is_{2}, X_{3}, X_{4}`4`,`B`._{1}= 4 - Since the median of
`X`is_{1}, X_{3}, X_{4}`3`,`B`._{2}= 3 - Since the median of
`X`is_{1}, X_{2}, X_{4}`3`,`B`._{3}= 3 - Since the median of
`X`is_{1}, X_{2}, X_{3}`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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 15 | 1s | 256MB | Minimum |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o manymedians -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512