CF1862G The Great Equalizer

Tema 买了一个旧设备，设备屏幕很小，侧面有一行已经磨损的字：“The Great Equalizer”。 卖家说，这个设备需要输入一个整数数组 $a$，然后“The Great Equalizer”会按如下方式工作： 1. 将当前数组按非递减顺序排序，并去除重复元素，只保留每个元素的一次出现。 2. 如果当前数组的长度等于 $1$，设备停止工作并输出数组中唯一的数字——这就是设备的输出值。 3. 向当前数组中的每个元素加上一个等差数列 $\{n, n-1, n-2, \ldots, 1\}$，其中 $n$ 是当前数组的长度。换句话说，对于从零开始编号的第 $i$ 个元素，加上 $n-i$。 4. 回到第一步。 为了测试设备的工作，Tema 想出了一个整数数组 $a$，然后想对数组 $a$ 执行 $q$ 次如下类型的操作： 1. 将 $a_i$（$1 \le i \le n$）赋值为 $x$（$1 \le x \le 10^9$）。 2. 将数组 $a$ 输入到设备中，查询设备的输出值，且在设备工作过程中数组 $a$ 保持不变。 请你帮助 Tema 求出每次操作后设备的输出值。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示 Tema 最初想出的数组 $a$ 的大小。 第二行包含 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示操作的数量。 接下来的 $q$ 行，每行包含两个整数 $i$（$1 \le i \le n$）和 $x$（$1 \le x \le 10^9$），表示一次操作的描述。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $q$ 个整数，分别表示每次操作后设备的输出值。

我们来看第一个输入示例。 最初输入到设备的数组为 $[6, 4, 8]$。变化过程如下：$[6, 4, 8] \rightarrow [4, 6, 8] \rightarrow [7, 8, 9] \rightarrow [10, 10, 10] \rightarrow [10]$。 然后，输入到设备的数组为 $[6, 10, 8]$。变化过程如下：$[6, 10, 8] \rightarrow [6, 8, 10] \rightarrow [9, 10, 11] \rightarrow [12, 12, 12] \rightarrow [12]$。 最后一次输入到设备的数组为 $[6, 10, 1]$。变化过程如下：$[6, 10, 1] \rightarrow [1, 6, 10] \rightarrow [4, 8, 11] \rightarrow [7, 10, 12] \rightarrow [10, 12, 13] \rightarrow [13, 14, 14] \rightarrow [13, 14] \rightarrow [15, 15] \rightarrow [15]$。 由 ChatGPT 4.1 翻译