問題文
あなたはカラオケ店員で、客が入る部屋を割り当てています。
\(1\) から \(N\) までの番号が付いた部屋があります。最初、\(N\) 個の部屋は空です。
\(Q\) 個のクエリが与えられるので、順番に処理してください。クエリは以下の2種類です。
1: 現在空いている部屋のうち、番号が最も小さい部屋に客を入れる。2 i: \(i\) 番目の部屋の客が退出する。3: 使用中の部屋の個数を出力する。
ただし、\(1\) 番目の形式のクエリにおいては、空き部屋が存在しない場合は客は帰るものとする。\(2\) 番目の形式のクエリにおいては、その部屋が必ず使用中であることが保証される。
制約
- \(1 ≤ N, Q ≤ 10^4\)
- \(2\) 番目の形式のクエリについて、\(1 ≤ i ≤ N\)
入力
入力は以下の形式で標準入力から与えられる。
\(N\) \(Q\)
\(query_1\)
\(query_2\)
\(\vdots\)
\(query_Q\)
ただし、\(query_q\) は\(q\) 個目のクエリを表しており、次のいずれかの形式で与えられる。
\(1\)
\(2\) \(i\)
\(3\)
出力
\(3\) 番目の形式のクエリに対し、順番に答えを改行で出力せよ。
入力例 1
4 9
1
1
1
2 2
3
2 1
3
1
3
出力例 1
2
1
2
クエリを順に処理していきます。
- \(1\) 番目の部屋に客が入る。
- \(2\) 番目の部屋に客が入る。
- \(3\) 番目の部屋に客が入る。
- \(2\) 番目の部屋の客が退出する。
- 使用中の部屋の個数を出力する。\(2\) を出力する。
- \(1\) 番目の部屋の客が退出する。
- 使用中の部屋の個数を出力する。\(1\) を出力する。
- \(1\) 番目の部屋に客が入る。
- 使用中の部屋の個数を出力する。\(2\) を出力する。
入力例 2
10 10
3
1
1
1
1
3
2 4
3
1
1
出力例 2
0
4
3
提出欄
実行結果
| ケース番号 | 結果 | 実行時間 (ms) | メモリ使用量 (KB) |
|---|