题目描述

小华管理一个仓库，支持四种操作：

1. in s：将编号为字符串 s（仅包含小写字母和数字，且各不相同）的产品入库。
2. out：将最晚入库的产品出库，并输出其编号；若仓库空，输出 EMPTY。
3. count：输出当前仓库中产品的数量。
4. check：输出仓库中编号按字典序最小的产品；若仓库空，输出 EMPTY。

要求在 $q\le 2\times10^5$ 次操作内高效完成上述四种操作。

解题思路

题目内容

小华是一个仓库管理员，他的日常就是管理仓库产品的入库出库。

有四种操作：

$in$ $s$，给一个只包含小写字符和数字的字符串 $s$ ，表示一个新的产品入库， 产品编号为 $s$ 。

$out$ ，表示一个出库请求，小华会将最晚入库的产品出库。

$count$ ，表示清点仓库里的产品数量。

$check$ ，表示查询仓库里编号字典序最小的产品。(字典序的顺序是先按照 第一个字符以升序排列;如果第一个字符一样，那就比较第二个、第三个 乃至后面的字母。如果比到最后两个串不一样长(比如，$123$ 和 $12345$ )，那么把短者排在前。)

输入描述

第一行一个整数 $q(1<=q<=200000)$ 表示操作的次数。

接下来 $q$ 行每行一个操作，为四种操作之一。

保证所有产品的编号都是仅包含数字和小写字母的字符串，每个字符串长 度不超过 $20$ 。

保证所有产品的编号互不相同。

输出描述

对于每个 $out$ 操作，输出一行，包含一个字符串，表示被出库的产品编号。

如果没有能出库的产品输出 $EMPTY$ 。

对于每个 $count$ 操作，输出一行，包含一个整数，表示当前仓库里的产品 数量。

样例1

输入

13
check
in c1
in c2
count
check
in b3
in b4
count
check
out
check
out
check

输出

EMPTY
2
c1
4
b3
b4
b3
b3
c1

说明

首先 $check$ 操作，此时仓库里没有产品输出 $EMPTY$。

后面 $in$ $c1$ $in$ $c2$ 两个操作，仓库中有 $c1$ ，$c2$ 两个产品，因此 $count$ 操 作，输出为 $2$ 。

$check$ 输出仓库里编号字典序最小的产品编号 $c1$。

然后 $in$ $b3$ $in$ $b4$ ，仓库中有 $c1，c2，b3，b4$ 四个产品，$count$ 操作输出 $4$ ，$check$ 输出仓库里编号字典序最小的产品编号 $b3$ ，$out$ 将最晚入 库的产品出库，输出 $b4$ ，$check$ 输出仓库里编号字典序最小的产品编号 $b 3$ 。$out$ 将最晚入库的产品出库，输出 $b3$ ，此时仓库只有 $c1，c2$ 两个 产品，$check$ 输出仓库里编号最小的产品编号 $c1$ 。