Score : 300 points
Problem Statement
When l is an odd number, the median of l numbers a1,a2,...,al is the (2l+1)-th largest value among a1,a2,...,al.
You are given N numbers X1,X2,...,XN, where N is an even number.
For each i=1,2,...,N, let the median of X1,X2,...,XN excluding Xi, that is, the median of X1,X2,...,Xi−1,Xi+1,...,XN be Bi.
Find Bi for each i=1,2,...,N.
Constraints
- 2≤N≤200000
- N is even.
- 1≤Xi≤109
- All values in input are integers.
Input is given from Standard Input in the following format:
N
X1 X2 ... XN
Output
Print N lines.
The i-th line should contain Bi.
4
2 4 4 3
4
3
3
4
- Since the median of X2,X3,X4 is 4, B1=4.
- Since the median of X1,X3,X4 is 3, B2=3.
- Since the median of X1,X2,X4 is 3, B3=3.
- Since the median of X1,X2,X3 is 4, B4=4.
2
1 2
2
1
6
5 5 4 4 3 3
4
4
4
4
4
4