CF1705E.Mark and Professor Koro

After watching a certain anime before going to sleep, Mark dreams of standing in an old classroom with a blackboard that has a sequence of $n$ positive integers $a_1, a_2,\dots,a_n$ on it.

Then, professor Koro comes in. He can perform the following operation:

• select an integer $x$ that appears at least $2$ times on the board,
• erase those $2$ appearances, and
• write $x+1$ on the board.

Professor Koro then asks Mark the question, "what is the maximum possible number that could appear on the board after some operations?"

Mark quickly solves this question, but he is still slower than professor Koro. Thus, professor Koro decides to give Mark additional challenges. He will update the initial sequence of integers $q$ times. Each time, he will choose positive integers $k$ and $l$, then change $a_k$ to $l$. After each update, he will ask Mark the same question again.

Help Mark answer these questions faster than Professor Koro!

Note that the updates are persistent. Changes made to the sequence $a$ will apply when processing future updates.

睡前观看某部动漫后，马克梦见自己站在一间古老的教室里，黑板上写着一个由 $n$ 个正整数 $a_1, a_2,\dots,a_n$ 构成的序列。

接着，Koro 教授走了进来。他可以执行如下操作：

• 选择一个在黑板上至少出现两次的整数 $x$，
• 擦去该整数的两个出现，
• 在黑板上写下 $x+1$。

随后，Koro 教授向马克提问：“经过若干次操作后，黑板上可能出现的最大数字是多少？”

马克很快便解答了这个问题，但他的速度仍不及 Koro 教授。于是，Koro 教授决定给马克增设额外挑战：他将对初始整数序列进行 $q$ 次更新。每次更新中，他选择正整数 $k$ 和 $l$，并将 $a_k$ 修改为 $l$。每次更新后，他都会再次向马克提出相同的问题。

请帮助马克比 Koro 教授更快地回答这些问题！

注意：这些更新是持久化的。对序列 $a$ 所做的修改将在后续所有更新中持续生效。

The first line of the input contains two integers $n$ and $q$ ($2\leq n\leq 2\cdot 10^5$, $1\leq q\leq 2\cdot 10^5$) — the length of the sequence $a$ and the number of updates, respectively.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1\leq a_i\leq 2\cdot 10^5$)

Then, $q$ lines follow, each consisting of two integers $k$ and $l$ ($1\leq k\leq n$, $1\leq l\leq 2\cdot 10^5$), telling to update $a_k$ to $l$.

输入的第一行包含两个整数 $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$。

Print $q$ lines. The $i$-th line should consist of a single integer — the answer after the $i$-th update.

输出 $q$ 行。第 $i$ 行应包含一个整数——即第 $i$ 次更新后的答案。

In the first example test, the program must proceed through $4$ updates.

The sequence after the first update is $[2,3,2,4,5]$. One sequence of operations that achieves the number $6$ the following.

• Initially, the blackboard has numbers $[2,3,2,4,5]$.
• Erase two copies of $2$ and write $3$, yielding $[3,4,5,\color{red}{3}]$.
• Erase two copies of $3$ and write $4$, yielding $[4,5,\color{red}{4}]$.
• Erase two copies of $4$ and write $5$, yielding $[5,\color{red}{5}]$.
• Erase two copies of $5$ and write $6$, yielding $[\color{red}{6}]$.

Then, in the second update, the array is changed to $[2,3,2,4,3]$. This time, Mark cannot achieve $6$. However, one sequence that Mark can use to achieve $5$ is shown below.

• Initially, the blackboard has $[2,3,2,4,3]$.
• Erase two copies of $2$ and write $3$, yielding $[3,4,3,\color{red}{3}]$.
• Erase two copies of $3$ and write $4$, yielding $[3,4,\color{red}{4}]$.
• Erase two copies of $4$ and write $5$, yielding $[3,\color{red}{5}]$.

In the third update, the array is changed to $[2,3,2,1,3]$. One way to achieve $4$ is shown below.

• Initially, the blackboard has $[2,3,2,1,3]$.
• Erase two copies of $3$ and write $4$, yielding $[2,2,1,\color{red}{4}]$.

在第一个样例测试中，程序必须执行 $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$。但 Mark 可以通过如下操作序列得到 $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}]$。