Hamako Online Judge

TLE
0.5sec

MLE
64MB

得点
10

問題

数列$A$が与えられる。
以下の$N$個のクエリに、与えられる順番で対応し、各クエリ終了後に数列$A$のmexを出力してください。
数列$A$のmexとは数列$A$に含まれない最小の非負整数のことを表す。
$i$番目のクエリは以下の形式で与えられます。

$Q_i$ $x_i$

・$Q_i$が0の場合、数列$A$の末尾に$x_i$を追加する。
・$Q_i$が1の場合、数列$A$の最初に現れる$x_i$を1つ削除する。

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

$N$ $M$
$Q_1$ $x_1$
$Q_2$ $x_2$
 :
$Q_N$ $x_N$

各クエリ終了後の数列$A$のmexを改行区切りで出力してください。

$1 \leq N \leq 5 \times 10^{6}$

$0 \leq M \leq 5 \times 10^{6}$

$0 \leq x_i \leq M$

$Q_i$ = 1が与えられたとき、数列$A$に$x_i$が必ず存在する。

入力はすべて整数

部分点1は以下の制約を満たす。(点数の20%)

$0 \leq M \leq 100$

部分点2は以下の制約を満たす。(点数の40%)

$Q_i$ = 0が与えられたとき、数列$A$に$x_i$が必ず存在しない。

0
2
1

1回目のクエリ終了後は$A$ = {1}なのでmex = 0。
2回目のクエリ終了後は$A$ = {0,1}なのでmex = 2。
3回目のクエリ終了後は$A$ = {0}なのでmex = 1。