AT_abc253_c [ABC253C] Max - Min Query

题目描述

维护一个数组 $s$。$s$ 初始为空。

按顺序执行 $q$ 个操作，每个操作都是以下三种之一：

• 1 x：将 $x$ 加入 $s$。
• 2 x c：将数组中的 $x$ 去除若干次。设 $d$ 为 $x$ 在 $s$ 中出现的次数，那么删除次数将为 $c,d$ 两数中的更小值。
• 3：输出数组中最大值与最小值的差。保证此时 $s$ 不为空。

输入格式

第一行输入一个整数 $q$。

接下来 $q$ 行，每行一个操作，格式如题。

输出格式

按顺序输出每个 $3$ 型询问的答案。每次回答完要换行。

输入输出样例 #1

输入 #1

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

输出 #1

1
5
4

输入输出样例 #2

输入 #2

4
1 10000
1 1000
2 100 3
1 10

输出 #2

说明/提示

数据规模与约定

对于全部测试点，数据保证：

• $1 \le c \le q \le 2 \times 10^5$；
• $0 \le x \le 10^9$；
• 输入的数值均为整数。