配点 : $500$ 点

問題文

空の列 $A$ があります。クエリが $Q$ 個与えられるので、与えられた順番に処理してください。 クエリは次の $3$ 種類のいずれかです。

• 1 x : $A$ の最後尾に $x$ を追加する。
• 2 : $A$ の最初の要素を出力する。その後、その要素を削除する。このクエリが与えられるとき、$A$ は空でないことが保証される。
• 3 : $A$ を昇順にソートする。

制約

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• クエリ 2 が与えられるとき、$A$ は空でない。
• 入力は全て整数である。

入力

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

$Q$

$\mathrm{query} 1$

$\mathrm{query} 2$

$\vdots$

$\mathrm{query} Q$

$i$ 番目のクエリ $\mathrm{query} i$ では、まずクエリの種類 $c_i$（ $1, 2, 3$ のいずれか）が与えられる。 $c_i = 1$ の場合はさらに整数 $x$ が追加で与えられる。

すなわち、各クエリは以下に示す $3$ つの形式のいずれかである。

$1$ $x$

$2$

$3$

出力

$c_i = 2$ を満たすクエリの回数を $q$ として $q$ 行出力せよ。 $j$ $(1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

8
1 4
1 3
1 2
1 1
3
2
1 0
2

1
2

入力例 $1$ において、 $i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

• $(4)$
• $(4, 3)$
• $(4, 3, 2)$
• $(4, 3, 2, 1)$
• $(1, 2, 3, 4)$
• $(2, 3, 4)$
• $(2, 3, 4, 0)$
• $(3, 4, 0)$

9
1 5
1 5
1 3
2
3
2
1 6
3
2

5
3
5

入力例 $2$ において、 $i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

• $(5)$
• $(5, 5)$
• $(5, 5, 3)$
• $(5, 3)$
• $(3, 5)$
• $(5)$
• $(5, 6)$
• $(5, 6)$
• $(6)$