06776. USACO·选举查询 未做

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

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

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

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

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

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

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

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

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

【样例解释】

• 测试点 5-7：$N,Q\le 3000$。

• 测试点 8-15：没有额外限制。

【数据规模与约定】

• 测试点 3-4：$N,Q\le 100$。

• 测试点 5-7：$N,Q\le 3000$。

• 测试点 8-15：没有额外限制。

供题：Chongtian Ma，Haokai Ma