!Please take care hints!"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 ai
. 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≤l≤r≤n
) to maximize the convenience equal to
max(al,al+1,…,ar)−min(al,al+1,…,ar)−(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
Each test consists of several test cases. The first line contains a single integer t
(1≤t≤104
) — 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≤n,q≤2⋅105
) — the number of sweaters and the number of size changes.

The second line of each test case contains n
integers a1,a2,…,an
(1≤ai≤109
) — the sizes of the sweaters.

Each of the following q
lines of each test case contains two integers p
and x
(1≤p≤n
, 1≤x≤109
) — 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⋅105
.

Output
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.

Example
InputCopy
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
OutputCopy
8
0
7
0
4
4
4
5
3
6
6
9
7
Note
Consider the first test case.

Before any changes, you can take all the sweaters; then the convenience is equal to max(a1,a2)−min(a1,a2)−(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 max(a1,a2)−min(a1,a2)−(2−1)=10−2−1=7
.!Hint 1: Utilize Efficient Data Structures for Range Queries
To maximize the convenience, which involves calculating the range (max - min) for various subsegments, you need a way to efficiently query the maximum and minimum values within any given range.

Segment Trees or Sparse Tables:
Implement a segment tree or a sparse table to perform range maximum and range minimum queries in logarithmic or constant time.
This allows you to quickly evaluate the convenience for different subsegments without recalculating max and min from scratch each time.
Preprocessing:
Preprocess the array to build these data structures before handling any queries or updates.
Efficient preprocessing ensures that subsequent queries can be answered swiftly, which is crucial given the potential number of changes.
By leveraging these data structures, you can handle range queries effectively, enabling you to evaluate the convenience for all possible subsegments quickly.Hint 2: Optimize Handling of Updates and Maintainability
Since the sweater sizes can change multiple times, it's essential to ensure that your solution can handle updates efficiently while still allowing quick queries for maximum convenience.

Dynamic Updates:
Choose data structures that support dynamic updates, such as segment trees with update operations, to reflect changes in sweater sizes promptly.
This ensures that after each update, you can still perform accurate range queries without rebuilding the entire structure.
Balancing Update and Query Efficiency:
Ensure that both update and query operations are optimized to run within acceptable time limits, especially when dealing with a large number of operations.
Consider the trade-offs between different data structures to find the most efficient approach for your specific use case.
By focusing on efficient update mechanisms and maintaining the integrity of your range queries, you can ensure that your solution remains performant even as the sweater sizes undergo multiple changes.!
c++