Description

给出一个长度为N的非负整数序列A_i，对于所有1 < = k < = (N + 1) / 2， 输出前1,3,5,…个数的中位数。

Format

Input

第1行为一个正整数N，表示了序列长度。

N<=10^5

第2行包含N个整数A_i

(-10^9 < = A_i < = 10^9)

Output

如题所示。

Samples

7
1 3 5 7 9 11 6

1
3
5
6