407007 - 中位数

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

输入

第一行一个正整数 N(1 ≤ N ≤ 10^5)。 第二行 N 个正整数 A1 … AN(0 ≤ Ai ≤10^9)。

输出

共 ⌊ (N + 1) /2 ⌋ 行,第 i 行为 A1 … A2i−1 的中位数。

样例

输入

7
1 3 5 7 9 11 6

输出

1
3
5
6

输入

7
3 1 5 9 8 7 6

输出

3
3
5
6
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题