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

 Bu sualda Azərbaycanca danış #include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class SegmentTree {
public:
    vector<int> st_max, st_min;
    int n;

    SegmentTree(int size) {
        n = size;
        st_max.resize(4 * n, INT_MIN);
        st_min.resize(4 * n, INT_MAX);
    }

    void build(const vector<int>& arr, int idx, int l, int r) {
        if (l == r) {
            st_max[idx] = arr[l];
            st_min[idx] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, 2 * idx + 1, l, mid);
            build(arr, 2 * idx + 2, mid + 1, r);
            st_max[idx] = max(st_max[2 * idx + 1], st_max[2 * idx + 2]);
            st_min[idx] = min(st_min[2 * idx + 1], st_min[2 * idx + 2]);
        }
    }

    void update(int idx, int l, int r, int pos, int val) {
        if (l == r) {
            st_max[idx] = val;
            st_min[idx] = val;
        } else {
            int mid = (l + r) / 2;
            if (pos <= mid) {
                update(2 * idx + 1, l, mid, pos, val);
            } else {
                update(2 * idx + 2, mid + 1, r, pos, val);
            }
            st_max[idx] = max(st_max[2 * idx + 1], st_max[2 * idx + 2]);
            st_min[idx] = min(st_min[2 * idx + 1], st_min[2 * idx + 2]);
        }
    }

    pair<int, int> query(int idx, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) {
            return {INT_MIN, INT_MAX}; // invalid range
        }
        if (ql <= l && qr >= r) {
            return {st_max[idx], st_min[idx]};
        }
        int mid = (l + r) / 2;
        auto left = query(2 * idx + 1, l, mid, ql, qr);
        auto right = query(2 * idx + 2, mid + 1, r, ql, qr);
        return {max(left.first, right.first), min(left.second, right.second)};
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // Initialize the segment tree
        SegmentTree st(n);
        st.build(a, 0, 0, n - 1);

        // Function to calculate maximum convenience for all subarrays
        auto calculate_convenience = [&]() {
            int max_convenience = INT_MIN;
            for (int l = 0; l < n; l++) {
                for (int r = l; r < n; r++) {
                    pair<int, int> result = st.query(0, 0, n - 1, l, r);
                    int max_size = result.first;
                    int min_size = result.second;
                    max_convenience = max(max_convenience, max_size - min_size - (r - l));
                }
            }
            return max_convenience;
        };

        // Initially calculate and print the maximum convenience
        int max_convenience = calculate_convenience();
        cout << max_convenience << endl;

        // Process each query
        while (q--) {
            int p, x;
            cin >> p >> x;
            p--; // Convert to 0-based index

            // Update the value in the segment tree
            st.update(0, 0, n - 1, p, x);

            // Recalculate and output the new maximum convenience
            max_convenience = calculate_convenience();
            cout << max_convenience << endl;
        }
}    }
bu kod doğru və zaman limitsiz işləyəcək?