配点 : $500$ 点

問題文

$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_{A_k}$ と $B_{A_k+1}$ の値を入れ替える。
• 全ての操作が終了した段階で、$B_j=1$ を満たす $j$ の値を $S_i$ と定義する。$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)$
• 入力は全て整数

入力

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

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_M$

出力

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

5 4
1 2 3 2

1
3
2
4

$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$

です。

3 3
2 2 2

1
1
1

10 10
1 1 1 9 4 4 2 1 3 3

2
2
2
3
3
3
1
3
4
4