300 - 大根堆

大根堆是堆的两种形式之一。 

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为最大堆,又称大顶堆。 

大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。 

现在,你需要编写一个程序,实现堆的一些操作。

输入

第一行是一个正整数n,代表接下来有n(n<=10^5)个操作。 

接下来n行。每行的格式为"pop"或者"push x",其中"pop"代表将堆顶元素输出,并删除堆顶元素。 

"push x"代表将一个正整数x(1<=x<=10^9)插入到堆中。 

输出

输出每次对应pop的值,如果堆为空,则输出"empty",否则输出相应的值,每个值占一行。

样例

输入

5
push 3
push 5
pop
pop
pop

输出

5
3
empty
时间限制 3 秒
内存限制 128 MB
讨论 统计
上一题 下一题