Problem 2. Election Queries

USACO 2025 US Open Contest, Gold

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。

Farmer John 有 $N$（$2 \leq N \leq 2 \cdot 10^5$）头奶牛，编号为 $1$ 到 $N$。一场选举正在 FJ 的农场上举行以确定两头新的头牛。初始时，已知奶牛 $i$ 将投票给奶牛 $a_i$（$1 \leq a_i \leq N$）。

为了确定两头头牛，FJ 将按以下过程进行选举：

• 选择他的奶牛们的任意子集 $S$，包含至少一头奶牛但并非包含所有奶牛。FJ 可以选择奶牛 $x$ 作为第一头头牛，如果她的票数是在 $S$ 中的所有奶牛的投票中出现次数最多的。
• FJ 可以选择奶牛 $y$ 作为第二头头牛，如果她的票数是不在 $S$ 中的所有奶牛的投票中出现次数最多的。
• 对于一个固定的子集 $S$，FJ 记头牛之间的多样性为 $|x - y|$。由于 FJ 不喜欢领导者具有相近的编号，他希望选择 $S$ 以最大化多样性。注意，如果 FJ 无法选出两头不同的头牛，则多样性为 $0$。

然而，一些奶牛不断改变主意，FJ 可能需要重新举行选举多次！因此，他向你提出 $Q$（$1 \leq Q \leq 10^5$）个查询。在每一个查询中，一头奶牛改变了她们的投票。在每一个查询过后，他向你询问新的头牛之间最大可能的

多样性

。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$ 和 $Q$。

以下一行包含 $a_1, a_2, \ldots, a_N$。

以下 $Q$ 行每行包含两个整数 $i$ 和 $x$，表示更新 $a_i = x$（$1 \leq i, x \leq N$）。

输出格式（输出至终端 / 标准输出）：

输出 $Q$ 行，其中第 $i$ 行包含前 $i$ 个查询过后最大可能的多样性。

输入样例：

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

输出样例：

4
3
2

在第一个查询过后，$a = [1, 2, 4, 4, 5]$。在选举的第一步中，FJ 可以选择 $S = \{1, 3\}$。在这里，奶牛 $1$ 收到一票，奶牛 $4$ 收到一票。因此，FJ 可以选择奶牛 $1$ 或奶牛 $4$ 中的任意一头作为第一头头牛。

对于不在这一选举中的所有奶牛，奶牛 $2$ 收到一票，奶牛 $4$ 收到一票，奶牛 $5$ 也收到一票。因此，FJ 可以选择奶牛 $2$，$4$ 或 $5$ 中的任意一头作为第二头头牛。

为了得到最大的多样性，FJ 可以选择奶牛 $1$ 作为第一头头牛，奶牛 $5$ 作为第二头头牛。因此，多样性为 $|1-5| = 4$。

在第二个查询过后，$a=[2,2,4,4,5]$，FJ 可以选择 $S = \{4, 5\}$。然后，他可以选择奶牛 $5$ 作为第一头头牛，奶牛 $2$ 作为第二头头牛。最大可能的多样性为 $|5 - 2| = 3$。

输入样例：

8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 4

输出样例：

4
4
4
7
7

测试点性质： 测试点 3-4：$N, Q \leq 100$。测试点 5-7：$N, Q \leq 3000$。测试点 8-15：没有额外限制。

供题：Chongtian Ma，Haokai Ma