Description

给你一个数字N，再给你N个数字,N是偶数

整个数列的中位数被认为是排序后第N/2个位置上的数字

问你：

如果去掉并且只去掉第1数字后，新数列中的中位数是多少?

如果去掉并且只去掉第2数字后，新数列中的中位数是多少?

如果去掉并且只去掉第3数字后，新数列中的中位数是多少?

如果去掉并且只去掉第n数字后，新数列中的中位数是多少?

Format

Input

一行给出数字N.

接下来一行N个数字Xi，代表这个数列

2≤N≤200000

N是一个偶数

1≤Xi≤10^9

Output

如题

Samples

4
2 4 4 3

4
3
3
4