Tema 买了一台旧设备,屏幕很小,侧面有一个破旧的铭文“伟大的均衡器”。
卖家说,设备需要输入一个整数数组 $$$a$$$ 作为输入,之后“伟大的均衡器”将按如下方式工作:
1. 按非降序对当前数组进行排序,并删除重复元素,只留下每个元素出现一次。
2. 如果数组的当前长度等于$$$1$$$,则设备停止工作并输出数组中的单个数字——设备的输出值。
3. 将等差数列 {$$$n,\ n - 1,\ n - 2,\ \ldots,\ 1$$$} 添加到当前数组,其中 $$$n$$$ 是当前数组的长度。换句话说,当索引从零开始时,$$$n - i$$$ 被添加到数组的第 $$$i$$$ 元素。
4. 转到第一步。
为了测试设备的操作,Tema 提出了某个整数数组 $$$a$$$,然后想要对以下类型的数组 $$$a$$$ 执行 $$$q$$$ 操作:
1. 将值 $$$x$$$ ($$$1 \le x \le 10^9$$$) 赋给元素 $$$a_i$$$ ($$$1 \le i \le n$$$)。
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$$$ 整数 - 每次操作后设备的输出值。
示例
输入 #1
4 3 2 4 8 3 1 6 2 10 3 1 5 1 2 2 2 2 1 5 3 2 5 6 7 1 2 1 7 1 7 2 5 1 2 2 7 2 2 5 2 5 1 10 6 10 1 7 4 8 2 5 1 4 2 8 3 4 1 9 3 7 3 4 3 1
输出 #1
10 12 15 4 10 8 8 9 8 12 2 14 12 12 11 11 10 11 10 11 14
注意
让我们考虑输入的第一个示例。
最初,作为设备输入给出的数字数组将为 $$$[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]$$$$$$