Gifts Order
Contest: Hello 2025
Difficulty rating: 2000
Tags: data structures, greedy, implementation, math, matrices

"T-Generation" has decided to purchase gifts for various needs; thus, they have $$$n$$$ different sweaters numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th sweater has a size of $$$a_i$$$. Now they need to send some subsegment of sweaters to an olympiad. It is necessary that the sweaters fit as many people as possible, but without having to take too many of them.

They need to choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) to maximize the convenience equal to $$$$$$\operatorname{max} (a_l, a_{l + 1}, \ldots, a_r) - \operatorname{min} (a_l, a_{l + 1}, \ldots, a_r) - (r - l),$$$$$$ that is, the range of sizes minus the number of sweaters.

Sometimes the sizes of the sweaters change; it is known that there have been $$$q$$$ changes, in each change, the size of the $$$p$$$-th sweater becomes $$$x$$$.

Help the "T-Generation" team and determine the maximum convenience among all possible pairs $$$(l, r)$$$ initially, as well as after each size change.

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of sweaters and the number of size changes.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the sizes of the sweaters.

Each of the following $$$q$$$ lines of each test case contains two integers $$$p$$$ and $$$x$$$ ($$$1 \le p \le n$$$, $$$1 \le x \le 10^9$$$) — the next size change.

It is guaranteed that the sum of the values of $$$n$$$ and the sum of the values of $$$q$$$ across all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the maximum value of convenience among all possible pairs $$$(l, r)$$$ before any actions, as well as after each size change.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Consider the first test case.

- Before any changes, you can take all the sweaters; then the convenience is equal to $$$\operatorname{max} (a_1, a_2) - \operatorname{min} (a_1, a_2) - (2 - 1) = 10 - 1 - 1 = 8$$$.
- After the first query, the sizes of both sweaters will be equal to $$$10$$$, you can only take the first sweater and the convenience is equal to $$$10 - 10 - 0 = 0$$$.
- After the second query, the size of the first sweater will be $$$10$$$, and the second $$$2$$$, you can take all the sweaters and the convenience is equal to $$$\operatorname{max} (a_1, a_2) - \operatorname{min} (a_1, a_2) - (2 - 1) = 10 - 2 - 1 = 7$$$.

Example input:
3
2 2
1 10
1 10
2 2
5 3
1 2 3 4 5
3 7
1 4
5 2
8 5
7 4 2 4 8 2 1 4
5 4
1 10
3 2
8 11
7 7

Example output:
8
0
7
0
4
4
4
5
3
6
6
9
7

Editorial:
To begin with, let's take a look at what an optimal segment of coats looks like. I claim that in the optimal answer, the maximum and minimum are located at the edges of the segment. Suppose this is not the case; then we can narrow the segment (from the side where the extreme element is neither the minimum nor the maximum), and the answer will improve since the length will decrease, while the minimum and maximum will remain unchanged.
Okay, there are two scenarios: when the minimum is at $$$l$$$ and the maximum is at $$$r$$$, and vice versa. These two cases are analogous, so let's consider the solution when the minimum is at $$$l$$$. Let's express what the value of the segment actually is: it is $$$a_r - a_l - (r - l) = (a_r - r) - (a_l - l)$$$, meaning there is a part that depends only on $$$r$$$ and a part that depends only on $$$l$$$. Let's create a segment tree where we will store the answer, as well as the maximum of all $$$a_i - i$$$ and the minimum of all $$$a_i - i$$$ (for the segment that corresponds to the current node of the segment tree, of course).
Now, let's see how to recalculate the values at the node. First, the minimum/maximum of $$$a_i - i$$$ can be easily recalculated by taking the minimum/maximum from the two children of the node in the segment tree. Now, how do we recalculate the answer? In fact, it is simply the maximum of the two answers for the children, plus (the maximum in the right child) minus (the minimum in the left child), which is the case when the maximum is in the right child and the minimum is in the left. Since we maintain this in the segment tree, we can easily handle update queries.
For greater clarity, I recommend looking at the code.