E - 作弊 Amidakuji

给定一个长度为 $M$ 的序列，它由 $1$ 到 $N-1$ 之间的整数组成：$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$ 之外的整数 $k$，按照升序排列）进行以下操作：
  • 交换 $B_{A_k}$ 和 $B_{A_k+1}$ 的值。
• 在所有操作完成后，令 $S_i$ 的值为满足 $B_j=1$ 的 $j$。求出 $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