前缀中位数

题目描述

给定一个整数序列 $a_1,a_2,\cdots,a_n$，计算出前一个数，前三个数，前五个数直到前 $n$ 个数的中位数。

所谓一些数的中位数，就是这些数字排序后位置在最中间的数。保证 $n$ 是一个奇数。

输入格式

第一行：单个整数表示 $n$，保证 $n$ 是奇数；

第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

共 $(n-1)/2+1$ 行：第 $i$ 行表示前 $2i-1$ 个数字的中位数。

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

样例输入 #2

5
4 3 1 4 2

样例输出 #2

4
3
3

数据范围

• $0 \le a_i \le 10^9$；
• 对于 30% 的数据，满足 $1\le n\le 500$；
• 对于 60% 的数据，满足 $1\le n\le 30000$；
• 对于 100% 的数据，满足 $1\le n\le 100000$。

测试点分布