时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个长度为 \(N\) 的非负整数序列 \(A\)，对于前奇数项求中位数。

【输入格式】

　　一行一个正整数 \(N\)。
　　第二行 \(N\) 个正整数 \(A_{1\dots N}\)。。

【输出格式】

　　共 \(\lfloor \frac{N + 1}2\rfloor\) 行，第 \(i\) 行为 \(A_{1\dots 2i - 1}\) 的中位数。

【输入输出样例1】

　Input

7
1 3 5 7 9 11 6

　Output

1
3
5
6

【输入输出样例2】

　Input

7
3 1 5 9 8 7 6

　Output

3
3
5
6

【数据限制】

　　对于 \(20\%\) 的数据，\(N \le 100\)；
　　对于 \(40\%\) 的数据，\(N \le 3000\)；
　　对于 \(80\%\) 的数据，\(1 \le N ≤ 200000\)，\(0 \le A_i \le 10^6\)。
　　对于 \(100\%\) 的数据，\(1 \le N ≤ 200000\)，\(0 \le A_i \le 10^9\)。

【来源】

　　Mr.he**