题目描述

整数の多重集合 $S$ があります。はじめ $S$ は空です。

$Q$ 個のクエリが与えられるので順に処理してください。 クエリは次の $3$ 種類のいずれかです。

• 1 x : $S$ に $x$ を $1$ 個追加する。
• 2 x c : $S$ から $x$ を $\mathrm{min}(c,$ $(S$ に含まれる $x$ の個数 $))$ 個削除する。
• 3 : $(S$ の最大値 $)-$ $(S$ の最小値 $)$ を出力する。このクエリを処理するとき、 $S$ が空でないことが保証される。

输入格式

入力は以下の形式で標準入力から与えられる。

$Q$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$

$i$ 番目のクエリを表す $\mathrm{query}_i$ は以下の $3$ 種類のいずれかである。

$1$ $x$

$2$ $x$ $c$

$3$

输出格式

3 のクエリに対する答えを順に改行区切りで出力せよ。

题目大意

题目描述

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

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

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

输入格式

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

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

输出格式

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

说明/提示

数据规模与约定

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

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

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

1
5
4

4
1 10000
1 1000
2 100 3
1 10

提示

制約

• $1\ \leq\ Q\ \leq\ 2\times\ 10^5$
• $0\ \leq\ x\ \leq\ 10^9$
• $1\ \leq\ c\ \leq\ Q$
• 3 のクエリを処理するとき、$S$ は空でない。
• 入力は全て整数

Sample Explanation 1

多重集合 $S$ は以下のように変化します。 - $1$ 番目のクエリ : $S$ に $3$ を追加する。$S$ は $\lbrace3\ \rbrace$ となる。 - $2$ 番目のクエリ : $S$ に $2$ を追加する。$S$ は $\lbrace2,\ 3\rbrace$ となる。 - $3$ 番目のクエリ : $S\ =\ \lbrace\ 2,\ 3\rbrace$ の最大値は $3$ 、最小値は $2$ なので、 $3-2=1$ を出力する。 - $4$ 番目のクエリ : $S$ に $2$ を追加する。$S$ は $\lbrace2,2,3\ \rbrace$ となる。 - $5$ 番目のクエリ : $S$ に $7$ を追加する。$S$ は $\lbrace2,\ 2,3,\ 7\rbrace$ となる。 - $6$ 番目のクエリ : $S\ =\ \lbrace2,2,3,\ 7\rbrace$ の最大値は $7$ 、最小値は $2$ なので、 $7-2=5$ を出力する。 - $7$ 番目のクエリ : $S$ に含まれる $2$ の個数は $2$ 個なので、 $\mathrm{min(2,3)}\ =\ 2$ 個の $2$ を $S$ から削除する。$S$ は $\lbrace3,\ 7\rbrace$ となる。 - $8$ 番目のクエリ : $S\ =\ \lbrace3,\ 7\rbrace$ の最大値は $7$ 、最小値は $3$ なので、 $7-3=4$ を出力する。

Sample Explanation 2

クエリ $3$ が含まれない場合、何も出力してはいけません。