题目描述

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

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

输入格式

第一行：单个整数表示 $n$，保证 $n$ 是奇数； 第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

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

7
1 3 5 7 9 11 6

1
3
5
6

5
4 3 1 4 2

4
3
3

数据范围

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