D. Gifts Order
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"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

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

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