该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

双份编号

题目描述

资料室里有 $N$ 份资料，第 $i$ 份资料的编号为 $A_i$。同一编号可以对应多份资料。

管理员依次进行 $Q$ 次修改。每次修改给出两个整数 $i$ 和 $x$，将第 $i$ 份资料的编号改为 $x$，这次修改会保留到后续操作中。

每次修改完成后，请找出当前出现次数不足两次的最小非负整数。一个编号没有出现或只出现一次，都属于“出现次数不足两次”；出现两次或更多次则不属于。

输入格式

第一行包含两个整数 $N,Q$，分别表示资料份数和修改次数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示各份资料最初的编号。

接下来 $Q$ 行，每行包含两个整数 $i,x$，表示一次修改。编号可以改成与原来相同的数。

所有输入均为整数，且满足：

• $1\le N,Q\le 2\times 10^5$；
• $0\le A_i\le 10^9$；
• 每次修改中，$1\le i\le N$，$0\le x\le 10^9$。

输出格式

输出 $Q$ 行，每行一个整数。第 $k$ 行表示第 $k$ 次修改完成后的答案。

输入输出样例

输入 #1

5 4
0 0 1 2 2
4 1
5 1
1 1000000000
1 0

输出 #1

2
2
0
2

输入 #2

1 2
0
1 0
1 1000000000

输出 #2

0
0

样例解释

样例 1 的第一次修改后，编号依次为 $0,0,1,1,2$。编号 $0$ 和 $1$ 都出现两次，编号 $2$ 只出现一次，所以答案为 $2$。第二次修改后，编号 $2$ 不再出现，答案仍为 $2$。

第三次修改后，编号 $0$ 只出现一次，答案变为 $0$。第四次修改使编号 $0$ 重新出现两次，答案恢复为 $2$。

样例 2 中只有一份资料，无论怎样修改，编号 $0$ 的出现次数都不足两次。