题目描述

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

输入描述

第一行一个整数 $N$（$1\le N\le10^5$），表示序列长度。

第二行 $N$ 个整数 $A_i$（$1\le A_i\le10^9$）。

输出描述

输出 $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 行（向下取整），第 $i$ 行为 $A_1$ 到 $A_{2i-1}$ 的中位数。

样例 1

7
1 3 5 7 9 11 6

1
3
5
6

样例 2

3
1 1 3

1
1

说明提示

$A_1$ 到 $A_1$ 的中位数为 1。

$A_1$ 到 $A_3$ 的中位数为 3。

$A_1$ 到 $A_5$ 的中位数为 5。

$A_1$ 到 $A_7$ 的中位数为 6。