暂无测试数据。

给出一个长度为奇数 $N$ 的非负整数序列 $A_i$，对于所有 $1 \le k \le {(N + 1)\over 2}$，输出 $A_1, A_3, \ldots, A_{2k - 1}$ 的中位数，即前 $1,3,5,\ldots$ 个数的中位数。

输入格式

第一行一个奇数 $N\ (1\le N \le 99999)$。

第二行 $N$ 个空格分隔的正整数 $A_i\ (1\le A_i \le 10^9)$。

输出格式

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

7
1 3 5 7 9 11 6

1
3
5
6