AT_agc017_c.[AGC017C] Snuke and Spells

有 $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 \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 翻译