Code来自 OMG_wc
有改动

#include <deque>
#include <cstdio>
#include <utility>

#define IL inline
#define RE register
#define INF int(1e6 + 10)

namespace {
    using std::deque;
    using std::pair;
    using std::make_pair;
}

int T, n, m;
int ans;
int a[INF];

IL int read()
{
    RE int s = 0;
    RE int w = 1;
    RE char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 3) + (s << 1) + ch - '0';
        ch = getchar();
    }

    return s * w;
}

int main()
{
    T = read();
    for (int Case = 1; Case <= T; Case ++) {
        deque < pair <int, int> > q1, q2;
        if (Case == 1) {
            n = read();
            for (int j = 1; j <= n; j++) {
                a[j] = read();
            }
        } else {
            m = read();
            for (int j = 1; j <= m; j++) {
                int x, y;
                x = read();
                y = read();
                a[x] = y;
            }
        }

        for (int i = 1; i <= n; i++) {
            q1.push_back({a[i], i});
        }
        
        while (true) {
            int x, y, id;
            if (q1.size() + q2.size() == 2) {
                ans = 1;
                break;
            }
            y = q1.front().first;
            q1.pop_front();
            if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
                x = q1.back().first;
                id = q1.back().second;
                q1.pop_back();
            } else {
                x = q2.back().first;
                id = q2.back().second;
                q2.pop_back();
            }
            pair<int, int> now = make_pair(x - y, id);
            if (q1.empty() || q1.front() > now) {
                int cnt = 0;
                ans = q1.size() + q2.size() + 2;
                while (true) {
                    cnt++;
                    if (q1.size() + q2.size() + 1 == 2) {
                        if (cnt % 2 == 0) {
                            ans--;
                        }
                        break;
                    }
                    int x2, id2;
                    if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
                        x = q1.back().first;
                        id = q1.back().second;
                        q1.pop_back();
                    } else {
                        x = q2.back().first;
                        id = q2.back().second;
                        q2.pop_back();
                    }
                    now = {x - now.first, id};
                    if ((q1.empty() || now < q1.front()) && (q2.empty() || now < q2.front())) { ;
                    } else {
                        if (cnt % 2 == 0) {
                            ans--;
                        }
                        break;
                    }
                }
                break;
            } else {
                q2.push_front(now);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}