AT_abc253_c [ABC253C] Max - Min Query

[problemUrl]: https://atcoder.jp/contests/abc253/tasks/abc253_c 整数の多重集合 $ 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` のクエリに対する答えを順に改行区切りで出力せよ。

### 制約 - $ 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 $ が含まれない場合、何も出力してはいけません。