题目描述

题目将以任意次序给出整数，当输入的整数是 $-1$ 时，输出当前序列的中位数并且删去这个中位数（注意不要插入 $-1$！），对于数列里有偶数项数时，输出较小的那个中位数。

输入格式

第一行包含一个正整数 $n$，表示数据个数。

接下来 $n$ 个整数 $t$，如果 $t$ 是正数，把它加入数列；如果 $t=-1$，那么输出当前数列中的中位数并且删去。

输出格式

对于每次询问，输出当前数列中的中位数。

15
1 9 10 2 5 1 18 -1 -1 4 3 -1 8 7 -1

5
2
4
7

提示

最多会有 $10^5$ 个整数加进数列，最多会有 $10^5$ 次询问。