题目描述

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

题目大意

给你两个数组 $A$ 和 $B$，初始时，$B_i=i$。

定义第 $k$ 次操作为 $\operatorname{swap}(B_{A_k},B_{A_k+1})$

定义 $S_i$ 为依次进行 $1$ 到 $m$ 除 $i$ 号操作外的所有操作后，数字 $1$ 在 $B$ 数组中的位置。

请依次输出 $S_i$ 。

5 4
1 2 3 2

1
3
2
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

提示

制約

• $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$ です。