题目描述

给定一个长度为$M$的序列$A=(A_1,A_2,\dots,A_M)$，其中的元素都是介于$1$和$N-1$之间的整数（包括$1$和$N-1$）。对于所有满足$i=1, 2, \dots, M$的情况，回答以下问题：

• 给定一个序列$B=(B_1,B_2,\dots,B_N)$。初始时，我们有$B_j=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$。

样例输入 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