题目描述

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

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_{1\ldots N}$。

输出格式

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

7
1 3 5 7 9 11 6

1
3
5
6

7
3 1 5 9 8 7 6

3
3
5
6

样例分析

对于样例 $1$，对于每个 $i$：

当 $i=1$，$\{1\}$ 的中位数是 $1$；

当 $i=2$，$\{1,3,5\}$ 的中位数是 $3$；

当 $i=3$，$\{1,3,5,7,9\}$ 的中位数是 $5$；

当 $i=4$，$\{1,3,5,7,9,11,6\}$ 的中位数是 $6$；

数据范围与提示

对于 $20\%$ 的数据：$N \le 100$；

对于 $40\%$ 的数据：$N \le 3000$；

对于 $100\%$ 的数据：$1 \le N \le 10^5$，$0 \le A_i \le 10^9$。