Big Wins! (hard version)

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

using ll = long long;

struct Node {
    int best = 0, pref = 0, suff = 0, sum = 0;
};

Node mergeNode(const Node& a, const Node& b) {
    Node c;
    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suff = max(b.suff, a.suff + b.sum);
    c.best = max({a.best, b.best, a.suff + b.pref});
    return c;
}

struct SegTree {
    int n = 0;
    vector<Node> st;

    SegTree(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        st.assign(4 * n + 4, Node());
    }

    void build(int v, int l, int r) {
        if (l == r) {
            st[v] = {1, 1, 1, 1};
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);
        st[v] = mergeNode(st[v * 2], st[v * 2 + 1]);
    }

    void update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            int x = max(val, 0);
            st[v] = {x, x, x, val};
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(v * 2, l, m, pos, val);
        else update(v * 2 + 1, m + 1, r, pos, val);
        st[v] = mergeNode(st[v * 2], st[v * 2 + 1]);
    }

    Node query(int v, int l, int r, int ql, int qr) {
        if (ql > qr) return Node();
        if (ql == l && qr == r) return st[v];
        int m = (l + r) / 2;
        return mergeNode(
            query(v * 2, l, m, ql, min(qr, m)),
            query(v * 2 + 1, m + 1, r, max(ql, m + 1), qr)
        );
    }
};

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 2);
        int mx = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mx = max(mx, a[i]);
        }

        vector<vector<int>> pos(mx + 1);
        for (int i = 1; i <= n; i++) pos[a[i]].push_back(i);

        vector<int> L(n + 1), R(n + 1), stk;

        a[0] = 0;
        stk.push_back(0);
        for (int i = 1; i <= n; i++) {
            while (stk.back() && a[stk.back()] >= a[i]) stk.pop_back();
            L[i] = stk.back() + 1;
            stk.push_back(i);
        }

        a[n + 1] = 0;
        stk.clear();
        stk.push_back(n + 1);
        for (int i = n; i >= 1; i--) {
            while (stk.back() != n + 1 && a[stk.back()] >= a[i]) stk.pop_back();
            R[i] = stk.back() - 1;
            stk.push_back(i);
        }

        SegTree seg(n);
        seg.build(1, 1, n);

        int med = 1;
        for (int p : pos[1]) seg.update(1, 1, n, p, -1);

        int ans = 0;
        for (int mn = 1; mn <= mx; mn++) {
            for (int p : pos[mn]) {
                while (med < mx) {
                    int left = seg.query(1, 1, n, L[p], p - 1).suff;
                    int right = seg.query(1, 1, n, p + 1, R[p]).pref;
                    int mid = (a[p] <= med ? -1 : 1);

                    if (left + mid + right < 0) break;

                    med++;
                    for (int q : pos[med]) seg.update(1, 1, n, q, -1);
                }
            }
            ans = max(ans, med - mn);
        }

        cout << ans << '\n';
    }

    return 0;
}