Description

给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[2], …, A[2k - 1]的中位数。即前1，3，5，……个数的中位数。

Input Format

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

第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。

Output Format

输出(N + 1) / 2行，第i行为A[1], A[2], …, A[2i – 1]的中位数。

Sample

样例输入：

7
1 3 5 7 9 11 6

样例输出：

1
3
5
6

Hint

对于20%的数据，N ≤ 100；

对于40%的数据，N ≤ 3000；

对于100%的数据，N ≤ 100000。