题目描述

给定一个整数序列 $a_1,a_2,\cdots,a_n$ ，其中 $n$ 为奇数。需要依次计算该序列前 1 个数、前 3 个数、前 5 个数……直到前 $n$ 个数的中位数。中位数是将一组数字排序后，位于最中间位置的数。

输入格式

• 第一行：一个整数 $n$ （保证 $n$ 是奇数），表示整数序列的长度。
• 第二行：$n$ 个整数，依次表示 $a_1,a_2,\cdots,a_n$ 。

输出格式

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

数据范围

• $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$ 。

样例

输入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