2068 - 动态求中位数

通过次数

10

提交次数

20

时间限制 : 1 秒
内存限制 : 128 MB

现在有一个空的容器,支持两种操作:

    “add x”:往容器中插入一个数x;

    “query”:输出容器中所有数的中位数(如果存在两个中位数,输出较小的那个)。

现在输入一个整数n(1≤n≤100000),接下来n行数据,每行可能是“add x”,其中x表示一个整数(1≤x≤10^9),表示往容器中插入一个数x;也有可能是“query”,这个时候就要求你输出目前为止该容器中的中位数,如果容器为空,输出“empty”。

输入

第一行一个整数n。 

接下来n行,每行可能是“add x”或者“query”。

输出

对于每个“query”,输出当前容器中的中位数,如果容器中元素个数为偶数则输出较小的那个中位数,如果容器为空则输出“empty”。

样例

输入

6
query
add 2
add 1
query
add 5
query

输出

empty
1
2