AT_abc279_e [ABC279E] Cheating Amidakuji

[problemUrl]: https://atcoder.jp/contests/abc279/tasks/abc279_e $ 1 $ 以上 $ N-1 $ 以下の整数からなる長さ $ M $ の数列 $ A=(A_1,A_2,\dots,A_M) $ が与えられます。 $ i=1,2,\dots,M $ について、以下の質問に答えてください。 - 数列 $ B=(B_1,B_2,\dots,B_N) $ がある。最初、各 $ j $ について $ B_j=j $ である。今から、$ k=1,2,\dots,i-1,i+1,\dots,M $ の順に以下の操作を行う （すなわち、$ i $ を除いた $ 1 $ 以上 $ M $ 以下の整数 $ k $ について、昇順に以下の操作を行う）。 - $ B_{A_k} $ と $ B_{A_k+1} $ の値を入れ替える。 - 全ての操作が終了した段階で、$ B_j=1 $ を満たす $ j $ の値を $ S_i $ と定義する。$ S_i $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_M $

$ M $ 行出力せよ。 $ i\ (1\leq\ i\ \leq\ M) $ 行目には、$ S_i $ の値を整数として出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N-1\ (1\leq\ i\ \leq\ M) $ - 入力は全て整数 ### Sample Explanation 1 $ i\ =\ 2 $ のとき、操作によって $ B $ は以下のように変化します。 - 最初、$ B\ =\ (1,2,3,4,5) $ - $ k=1 $ として操作を行う。すなわち $ B_1 $ と $ B_2 $ の値を入れ替えて、$ B\ =\ (2,1,3,4,5) $ - $ k=3 $ として操作を行う。すなわち $ B_3 $ と $ B_4 $ の値を入れ替えて、$ B\ =\ (2,1,4,3,5) $ - $ k=4 $ として操作を行う。すなわち $ B_2 $ と $ B_3 $ の値を入れ替えて、$ B\ =\ (2,4,1,3,5) $ 全ての操作が終了した段階で $ B_3=1 $ であるため、$ S_2\ =\ 3 $ です。 同様に、 - $ i=1 $ のとき：$ k=2,3,4 $ の順に操作を行うと $ B=(1,4,3,2,5) $ になるので、$ S_1=1 $ - $ i=3 $ のとき：$ k=1,2,4 $ の順に操作を行うと $ B=(2,1,3,4,5) $ になるので、$ S_3=2 $ - $ i=4 $ のとき：$ k=1,2,3 $ の順に操作を行うと $ B=(2,3,4,1,5) $ になるので、$ S_4=4 $ です。