题目描述

有 $N$ 个球排成一排。第 $i$ 个球上最初写着一个整数 $A_i$。

すぬけ君会施展魔法，使这些球按照如下方式消失：

• 当球的数量恰好为 $k$ 个时，所有写有 $k$ 的球会同时消失。

すぬけ君的目标是通过施展若干次魔法，使所有球全部消失。由于有些情况下无法实现目标，因此すぬけ君希望通过修改尽可能少的球上的整数，使目标得以实现。

已知这些球上写的整数会自然变化共 $M$ 次。第 $j$ 次变化中，从左到右第 $X_j$ 个球上的整数会变成 $Y_j$。

对于每次变化后，在下一次变化发生之前，すぬけ君要达成目标，至少需要修改多少个球上的整数？请输出每次变化后所需的最小修改次数。假设すぬけ君可以极快地完成整数的修改。但请注意，他实际上并不需要真的进行修改。

输入格式

输入通过标准输入，格式如下：

$N\ M\ A\_1\ A\_2\ ...\ A\_N\ X\_1\ Y\_1\ X\_2\ Y\_2\ ...\ X\_M\ Y\_M$

输出格式

输出 $M$ 行。第 $j$ 行输出第 $j$ 次变化后，为实现目标最少需要修改多少个球上的整数。

样例 1

输入

5 3
1 1 3 4 5
1 2
2 5
5 4

输出

0
1
1

样例 2

输入

4 4
4 4 4 4
4 1
3 1
1 1
2 1

输出

0
1
2
3

样例 3

输入

10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7

输出

1
0
1
2
2
3
3
3
3
2

说明/提示

数据范围

• $1 \leq N \leq 200000$
• $1 \leq M \leq 200000$
• $1 \leq A_i \leq N$
• $1 \leq X_j \leq N$
• $1 \leq Y_j \leq N$

部分分

• 有 $500$ 分的测试数据满足 $N \leq 200$ 且 $M \leq 200$。

样例说明 1

• 第 $1$ 次变化后，球上的整数（自左至右）依次为 $2, 1, 3, 4, 5$。此时すぬけ君施展 $5$ 次魔法后，所有球都能消失，因此需要修改 $0$ 个球上的整数。
• 第 $2$ 次变化后，球上的整数依次为 $2, 5, 3, 4, 5$。此时至少需要修改 $1$ 个球上的整数。例如，将从左到右第 $5$ 个球的数改为 $2$ 后，すぬけ君施展 $4$ 次魔法就能让所有球消失。
• 第 $3$ 次变化后，球上的整数依次为 $2, 5, 3, 4, 4$。此时也至少需要修改 $1$ 个球上的整数。例如，将从左到右第 $3$ 个球的数改为 $2$ 后，すぬけ君施展 $3$ 次魔法即可清空所有球。

由 ChatGPT 5 翻译