310631: CF1862G. The Great Equalizer
Description
Tema bought an old device with a small screen and a worn-out inscription "The Great Equalizer" on the side.
The seller said that the device needs to be given an array $a$ of integers as input, after which "The Great Equalizer" will work as follows:
- Sort the current array in non-decreasing order and remove duplicate elements leaving only one occurrence of each element.
- If the current length of the array is equal to $1$, the device stops working and outputs the single number in the array — output value of the device.
- Add an arithmetic progression {$n,\ n - 1,\ n - 2,\ \ldots,\ 1$} to the current array, where $n$ is the length of the current array. In other words, $n - i$ is added to the $i$-th element of the array, when indexed from zero.
- Go to the first step.
To test the operation of the device, Tema came up with a certain array of integers $a$, and then wanted to perform $q$ operations on the array $a$ of the following type:
- Assign the value $x$ ($1 \le x \le 10^9$) to the element $a_i$ ($1 \le i \le n$).
- Give the array $a$ as input to the device and find out the result of the device's operation, while the array $a$ remains unchanged during the operation of the device.
Help Tema find out the output values of the device after each operation.
InputThe first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Then follows the description of each test case.
The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array $a$ that Tema initially came up with.
The second line of each test case contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.
The third line of a set contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of operations.
Each of the next $q$ lines of a test case contains two integers $i$ ($1 \le i \le n$) and $x$ ($1 \le x \le 10^9$) - the descriptions of the operations.
It is guaranteed that the sum of the values of $n$ and the sum of the values of $q$ for all test cases do not exceed $2 \cdot 10^5$.
OutputFor each test case, output $q$ integers — the output values of the device after each operation.
ExampleInput4 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 1Output
10 12 15 4 10 8 8 9 8 12 2 14 12 12 11 11 10 11 10 11 14Note
Let's consider the first example of the input.
Initially, the array of numbers given as input to the device will be $[6, 4, 8]$. It will change as follows: $$[6, 4, 8] \rightarrow [4, 6, 8] \rightarrow [7, 8, 9] \rightarrow [10, 10, 10] \rightarrow [10]$$
Then, the array of numbers given as input to the device will be $[6, 10, 8]$. It will change as follows: $$[6, 10, 8] \rightarrow [6, 8, 10] \rightarrow [9, 10, 11] \rightarrow [12, 12, 12] \rightarrow [12]$$
The last array of numbers given as input to the device will be $[6, 10, 1]$. It will change as follows: $$[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]$$
Output
Tema购买了一个带有小屏幕和模糊字样"The Great Equalizer"的旧设备。该设备需要输入一个整数数组a,然后按照以下步骤操作:
1. 将当前数组按非递减顺序排序,并删除重复元素,只保留每个元素的一个实例。
2. 如果当前数组的长度等于1,设备停止工作并输出数组中的单个数字——设备的输出值。
3. 将等差数列{n, n-1, n-2, …, 1}添加到当前数组中,其中n是当前数组的长度。换句话说,当从零开始索引时,将n-i添加到数组的第i个元素中。
4. 转到第一步。
为了测试设备的运行,Tema想出了一个整数数组a,然后想在数组a上执行q个操作,操作类型如下:
1. 将值x(1≤x≤10^9)赋给元素a_i(1≤i≤n)。
2. 将数组a作为输入提供给设备,并找出设备操作的输出结果,同时在设备运行过程中数组a保持不变。
帮助Tema找出设备在每次操作后的输出值。
输入数据格式:
第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。
接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n(1≤n≤2×10^5)——Tema最初想到的数组a的大小。
每个测试用例的第二行包含n个整数a_1, a_2, a_3, …, a_n(1≤a_i≤10^9)——数组a的元素。
每个测试用例的第三行包含一个整数q(1≤q≤2×10^5)——操作的数量。
每个测试用例的接下来q行,每行包含两个整数i(1≤i≤n)和x(1≤x≤10^9)——操作的描述。
保证所有测试用例的n值和q值的总和不超过2×10^5。
输出数据格式:
对于每个测试用例,输出q个整数——设备在每次操作后的输出值。题目大意: Tema购买了一个带有小屏幕和模糊字样"The Great Equalizer"的旧设备。该设备需要输入一个整数数组a,然后按照以下步骤操作: 1. 将当前数组按非递减顺序排序,并删除重复元素,只保留每个元素的一个实例。 2. 如果当前数组的长度等于1,设备停止工作并输出数组中的单个数字——设备的输出值。 3. 将等差数列{n, n-1, n-2, …, 1}添加到当前数组中,其中n是当前数组的长度。换句话说,当从零开始索引时,将n-i添加到数组的第i个元素中。 4. 转到第一步。 为了测试设备的运行,Tema想出了一个整数数组a,然后想在数组a上执行q个操作,操作类型如下: 1. 将值x(1≤x≤10^9)赋给元素a_i(1≤i≤n)。 2. 将数组a作为输入提供给设备,并找出设备操作的输出结果,同时在设备运行过程中数组a保持不变。 帮助Tema找出设备在每次操作后的输出值。 输入数据格式: 第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n(1≤n≤2×10^5)——Tema最初想到的数组a的大小。 每个测试用例的第二行包含n个整数a_1, a_2, a_3, …, a_n(1≤a_i≤10^9)——数组a的元素。 每个测试用例的第三行包含一个整数q(1≤q≤2×10^5)——操作的数量。 每个测试用例的接下来q行,每行包含两个整数i(1≤i≤n)和x(1≤x≤10^9)——操作的描述。 保证所有测试用例的n值和q值的总和不超过2×10^5。 输出数据格式: 对于每个测试用例,输出q个整数——设备在每次操作后的输出值。