作弊的阿弥陀签

题目描述

给你一个长度为 $M$ 的序列 $A=(A_1,A_2,\dots,A_M)$,其中每个元素都是介于 $1$ 和 $N-1$ 之间的整数。

请对每个 $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}$ 的值。

在所有操作结束后,设 $S_i$ 为满足 $B_j=1$ 的 $j$ 的值。求出 $S_i$。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_M$

输出格式

输出 $M$ 行。

第 $i$ 行 $(1\le i \le 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

数据范围

• $2 \le N \le 2\times 10^5$
• $1 \le M \le 2\times 10^5$
• $1 \le A_i \le N-1\ (1\le i \le M)$
• 输入中的所有值均为整数。