中位数

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

7
1 3 5 7 9 11 6

输出样例 #1

1
3
5
6

输入样例 #2

7
3 1 5 9 8 7 6

输出样例 #2

3
3
5
6

说明

对于 $20\%$ 的数据,$N \le 100$; 对于 $40\%$ 的数据,$N \le 3000$; 对于 $100\%$ 的数据,$1 \le N ≤ 100000$,$0 \le A_i \le 10^9$。