問題文

$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$ を求めよ。

制約

• $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$ の値を整数として出力せよ。

入力例 1

5 4
1 2 3 2

出力例 1

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$

です。

入力例 2

3 3
2 2 2

出力例 2

1
1
1

入力例 3

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

出力例 3

2
2
2
3
3
3
1
3
4
4