手写小根堆

难度：T2

【知识点：二叉堆的结构实现】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

开始时容器为空。每次插入都增加一个元素，相同数值可以出现多次。取出操作只删除一个元素；容器为空时输出 EMPTY，容器仍为空。

输入格式

输入$q$，之后$q$行操作：$1$ $x$插入$x$；$2$读取并删除最小值。

输出格式

每次操作$2$输出删除值；空堆输出EMPTY。

数据范围

$1\le q\le 100000$，$|x|\le 10^9$；允许在空堆执行操作$2$。

样例输入

7
1 3
1 7
1 9
1 1
2
2
2

样例输出

1
3
7

样例输入 2

7
1 7
1 2
1 7
2
2
2
2

样例输出 2

2
7
7
EMPTY

样例说明 2

两个 $7$ 是两次插入的两个元素，分别被取出；第四次取出时容器已空。