最大值减最小值查询

题目描述

我们有一个初始为空的整数多重集合 $S$。

给定 $Q$ 个查询，请按顺序处理它们。

每个查询是以下类型之一。

• 1 x：向 $S$ 中插入一个 $x$。
• 2 x c：从 $S$ 中删除 $m$ 个 $x$，其中 $m = \mathrm{min}(c,$ $S$ 中包含的 $x$ 的个数$)$。
• 3：打印 $(S$ 的最大值$)-(S$ 的最小值$)$。保证给出该查询时 $S$ 非空。

输入格式

输入按以下格式从标准输入给出：

Q
query_1
⋮
query_Q

第 $i$ 个查询 $\mathrm{query}_i$ 是以下格式之一：

1 x

2 x c

3

输出格式

按给出的顺序打印所有类型 3 查询的答案，每个答案占一行。

样例

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

1
5
4

多重集合 $S$ 的变化过程如下。

第 1 个查询：向 $S$ 中插入 3。此时 $S$ 为 $\lbrace 3 \rbrace$。

第 2 个查询：向 $S$ 中插入 2。此时 $S$ 为 $\lbrace 2, 3 \rbrace$。

第 3 个查询：$S = \lbrace 2, 3\rbrace$ 的最大值为 3、最小值为 2，因此打印 $3-2=1$。

第 4 个查询：向 $S$ 中插入 2。此时 $S$ 为 $\lbrace 2,2,3 \rbrace$。

第 5 个查询：向 $S$ 中插入 7。此时 $S$ 为 $\lbrace 2, 2,3, 7\rbrace$。

第 6 个查询：$S = \lbrace 2,2,3, 7\rbrace$ 的最大值为 7、最小值为 2，因此打印 $7-2=5$。

第 7 个查询：由于 $S$ 中有两个 2，且 $\mathrm{min(2,3)} = 2$，所以从 $S$ 中删除两个 2。此时 $S$ 为 $\lbrace 3, 7\rbrace$。

第 8 个查询：$S = \lbrace 3, 7\rbrace$ 的最大值为 7、最小值为 3，因此打印 $7-3=4$。

4
1 10000
1 1000
2 100 3
1 10

如果给定查询中不包含类型 3 的查询，则什么都不打印。

数据范围

• $1 \le Q \le 2 \times 10^5$
• $0 \le x \le 10^9$
• $1 \le c \le Q$
• 给出类型 3 的查询时，$S$ 非空。
• 输入中的所有值均为整数。