CF1705E Mark and Professor Koro

在睡前看了一部动漫后，Mark 梦见自己站在一间老旧的教室里，黑板上写着一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。 这时，Koro 教授走了进来。他可以进行如下操作： - 选择一个在黑板上至少出现了 $2$ 次的整数 $x$， - 擦掉这两个 $x$， - 在黑板上写下 $x+1$。 然后，Koro 教授问 Mark：“经过若干次操作后，黑板上可能出现的最大整数是多少？” Mark 很快就解出了这个问题，但他还是比 Koro 教授慢。因此，Koro 教授决定给 Mark 更多的挑战。他会对初始的整数序列进行 $q$ 次更新。每次，他会选择正整数 $k$ 和 $l$，然后将 $a_k$ 改为 $l$。每次更新后，他都会再次问 Mark 同样的问题。 请你帮助 Mark，比 Koro 教授更快地回答这些问题！ 注意，更新是持续生效的。对序列 $a$ 的更改会影响后续的所有更新。

输入的第一行包含两个整数 $n$ 和 $q$（$2\leq n\leq 2\cdot 10^5$，$1\leq q\leq 2\cdot 10^5$），分别表示序列 $a$ 的长度和更新次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i\leq 2\cdot 10^5$）。 接下来 $q$ 行，每行包含两个整数 $k$ 和 $l$（$1\leq k\leq n$，$1\leq l\leq 2\cdot 10^5$），表示将 $a_k$ 改为 $l$。

输出 $q$ 行，第 $i$ 行输出一次更新后的答案，即该次更新后黑板上可能出现的最大整数。

在第一个样例测试中，程序需要处理 $4$ 次更新。 第一次更新后，序列变为 $[2,3,2,4,5]$。一种能得到 $6$ 的操作序列如下： - 初始黑板上的数字为 $[2,3,2,4,5]$。 - 擦掉两个 $2$，写下 $3$，得到 $[3,4,5,\color{red}{3}]$。 - 擦掉两个 $3$，写下 $4$，得到 $[4,5,\color{red}{4}]$。 - 擦掉两个 $4$，写下 $5$，得到 $[5,\color{red}{5}]$。 - 擦掉两个 $5$，写下 $6$，得到 $[\color{red}{6}]$。 第二次更新后，数组变为 $[2,3,2,4,3]$。这次 Mark 无法得到 $6$，但可以通过如下操作得到 $5$： - 初始黑板上的数字为 $[2,3,2,4,3]$。 - 擦掉两个 $2$，写下 $3$，得到 $[3,4,3,\color{red}{3}]$。 - 擦掉两个 $3$，写下 $4$，得到 $[3,4,\color{red}{4}]$。 - 擦掉两个 $4$，写下 $5$，得到 $[3,\color{red}{5}]$。 第三次更新后，数组变为 $[2,3,2,1,3]$。一种得到 $4$ 的方法如下： - 初始黑板上的数字为 $[2,3,2,1,3]$。 - 擦掉两个 $3$，写下 $4$，得到 $[2,2,1,\color{red}{4}]$。 由 ChatGPT 4.1 翻译