#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
public:
    int n;
    vector<int> maxTree, minTree;

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

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) {
            maxTree[v] = a[tl];
            minTree[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, v * 2, tl, tm);
            build(a, v * 2 + 1, tm + 1, tr);
            maxTree[v] = max(maxTree[v * 2], maxTree[v * 2 + 1]);
            minTree[v] = min(minTree[v * 2], minTree[v * 2 + 1]);
        }
    }

    void update(int v, int tl, int tr, int pos, int newVal) {
        if (tl == tr) {
            maxTree[v] = newVal;
            minTree[v] = newVal;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) {
                update(v * 2, tl, tm, pos, newVal);
            } else {
                update(v * 2 + 1, tm + 1, tr, pos, newVal);
            }
            maxTree[v] = max(maxTree[v * 2], maxTree[v * 2 + 1]);
            minTree[v] = min(minTree[v * 2], minTree[v * 2 + 1]);
        }
    }

    pair<int, int> query(int v, int tl, int tr, int l, int r) {
        if (l > r) return {INT_MIN, INT_MAX};
        if (l == tl && r == tr) {
            return {maxTree[v], minTree[v]};
        }
        int tm = (tl + tr) / 2;
        auto left = query(v * 2, tl, tm, l, min(r, tm));
        auto right = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
        return {max(left.first, right.first), min(left.second, right.second)};
    }
};

void solve() {
    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];
        }

        SegmentTree segTree(n);
        segTree.build(a, 1, 0, n - 1);

        auto getMaxConvenience = [&]() -> int {
            int maxConvenience = INT_MIN;
            for (int l = 0; l < n; l++) {
                for (int r = l; r < n; r++) {
                    auto [mx, mn] = segTree.query(1, 0, n - 1, l, r);
                    int convenience = mx - mn - (r - l);
                    maxConvenience = max(maxConvenience, convenience);
                }
            }
            return maxConvenience;
        };

        cout << getMaxConvenience() << "\n";

        for (int i = 0; i < q; i++) {
            int p, x;
            cin >> p >> x;
            segTree.update(1, 0, n - 1, p - 1, x);
            cout << getMaxConvenience() << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}