题目描述

在长度为$n$的序列上，有$n$个$0$，他们的标号从$1$到$n$。现在，有$m$次突变，每次可以将标号为$x$的点变成$1$，如果本来就是$1$，就不会有任何变化产生。现在，对于每一次突变，我们想知道标号最小的$0$的标号是多少？

输入格式

第一行输入两个整数$n, m(1≤n≤10^7, 1≤m<min(5\times10^6, n))$。

接下去$m$行，每行一个整数$x(1≤x≤n)$。

输出格式

对于每次突变，输出标号最小的$0$的标号。

样例

10 5
3
2
1
6
4

1
1
4
4
5

提示

inline int read()
{
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + c - '0'; c = getchar();}
return x;
}

来源

2022 HGNU-SWUT暑假联合集训