AT_abc330_e [ABC330E] Mex and Update

[problemUrl]: https://atcoder.jp/contests/abc330/tasks/abc330_e 長さ $ N $ の数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 以下の $ Q $ 個のクエリに、与えられる順番で対応してください。 $ k $ 番目のクエリは以下の形式で与えられます。 > $ i_k $ $ x_k $ - まず、 $ A_{i_k}\ =\ x_k $ と変更する。この変更は以降のクエリにも引き継がれる。 - その後、 $ A $ の $ \rm{mex} $ を出力する。 - $ A $ の $ \rm{mex} $ とは、 $ A $ に含まれない最小の非負整数を指す。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ i_1 $ $ x_1 $ $ i_2 $ $ x_2 $ $ \vdots $ $ i_Q $ $ x_Q $

全体で $ Q $ 行出力せよ。 そのうち $ k $ 行目には $ k $ 番目のクエリに対する答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \le\ N,Q\ \le\ 2\ \times\ 10^5 $ - $ 0\ \le\ A_i\ \le\ 10^9 $ - $ 1\ \le\ i_k\ \le\ N $ - $ 0\ \le\ x_k\ \le\ 10^9 $ ### Sample Explanation 1 最初、数列 $ A $ は $ (2,0,2,2,1,1,2,5) $ です。 この入力では、 $ 5 $ つのクエリを処理します。 - $ 1 $ 番目のクエリで $ A_4\ =\ 3 $ と変更し、 $ A=(2,0,2,3,1,1,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 4 $ です。 - $ 2 $ 番目のクエリで $ A_4\ =\ 4 $ と変更し、 $ A=(2,0,2,4,1,1,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 3 $ です。 - $ 3 $ 番目のクエリで $ A_6\ =\ 3 $ と変更し、 $ A=(2,0,2,4,1,3,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 6 $ です。 - $ 4 $ 番目のクエリで $ A_8\ =\ 1000000000 $ と変更し、 $ A=(2,0,2,4,1,3,2,1000000000) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 5 $ です。 - $ 5 $ 番目のクエリで $ A_2\ =\ 1 $ と変更し、 $ A=(2,1,2,4,1,3,2,1000000000) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 0 $ です。