Description

由于某些原因，刘老板被一群原始人抓到要作为祭品。不幸的是他发现不只他一人被抓，还有很多现代人被原始人关在笼子里。刘老板向先被抓的人打听到一个消息：明天原始人们将要举行神秘的献祭，原始人会将所有现代人排成一排，并给每个人发放一个记有非负整数的叶子，然后按刚刚排好的顺序，从第一个人开始随机连续选取奇数个人，将被选人中所持有中位数的叶子作为幸运儿留下，剩余所有人将作为祭品献给原始人信奉的神，而幸运儿会重新获得自由。

刘老板作为一位想让机器不用电都能工作的大资本家，自然想要成为幸运儿活下来。他想到个主意，只要比所有人更先算出中位数并抢来相应的叶子，那他就可以活下来。现在，稳妥的刘老板拜托你帮他完成一个的程序，要求能将给定个数$N$的序列$M$中的所有前奇数项的中位数都求出来。

Input Format

第一行一个正整数$n$，代表一共有多少人。

第二行n个正整数$M_1\cdots_n$，代表所发放的数字。

题目得数据范围：$1 \le n \le 10^5$、任意叶片上的数字$0 \le M_i \le 10^9$。

Output Format

共 $\lfloor \frac{N+1}{2} \rfloor$ 行，第i行表示前$M_1\cdots_{2i-1}$中的符合要求的叶子上的值。

7
1 3 5 7 9 11 6

1
3
5
6

Source

Online Judge http://127.0.0.1