题目背景

某一天 $ZY$ 在无聊的时候阅读初中数学课本时候看到了数据与统计这一章，想起了还有周赛题目要出，然后选择了中位数这个知识点来 "水" 一题。

我们现在给出中位数的计算方法。

对于一个长度为 $N$ 的数列 $A_i$ 先进行从小到大排序得到一组数据 $X_1$ ,$X_2$ $...$ $X_n$ ，其中位数 $M_e$ 的计算公式如下：

题目描述

现给定一个数列 $A_i$ 该数列的长度为 $N$ ，现在我们要输出前奇数个数字的中位数 , 即前 $1$ , $3$ , $5$ , $…$ 个数的中位数。

输入格式

从文件 sequence.in 中读入数据。

第 $1$ 行为一个数字 $N$ 代表该数列的长度。

第 $2$ 行给定 $N$ 个数字 $A_i (A_i \in N^*)$ 。

输出格式

输出到文件 sequence.out 中。

共 $\frac{(N + 1)}{2}$行，第 $i$ 行为 $A_1$ ,$A_3$ , $…$, $A_{2k - 1}$ 的中位数。

测试样例

8
2 5 8 9 12 15 15 18

2
5
8
9

7
2 8 8 8 9 9 15

2
8
8
8

样例 1 解释

前 $1$ 个数字中的中位数为 $2$。

前 $3$ 个数字中的中位数为 $5$。

前 $5$ 个数字中的中位数为 $8$。

前 $7$ 个数字中的中位数为 $9$。

样例三

见附加文件下的 number3.in 与 number3.ans

数据规模与约定

• 对于 $60\%$ 的数据保证：$N \le 4000$ , $0 < A_i \le 3 \times 10^8$ 。
• 对于 $100\%$ 的数据保证：$N \le 2 \times 10^5$ , $0 < A_i \le 3 \times 10^8$ 。