思路都在注释里。

#include <bits/stdc++.h>
using namespace std;
const int N = 1100000;
int t, n, a[N];
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int main() {
	t = read();
	for (int now = 1; now <= t; now++) {
		if (now == 1) {
			n = read();
			for (int i = 1; i <= n; i++) {
				a[i] = read();
			}
		} else {
			int k, x, y;
			k = read();
			for (int i = 1; i <= k; i++) {
				x = read(), y = read();
				a[x] = y;
			}
		}
		deque<pair<int, int> > q1, q2;
		for (int i = 1; i <= n; i++) {
			q1.push_back(make_pair(a[i], i));
		}
		//q1原始蛇队列；q2新蛇队列。均 [小=>大] 有序
		int ans;
		while (1) {
			if (q1.size() + q2.size() == 2) {//如果只有两条蛇了，那么一条吃一条，答案是1
				ans = 1;
				break;
			}
			int mx, id, mn;
			mn = q1.front().first;//q1的头一定比q2的头小，否则会进入底下的if循环
			q1.pop_front();
			if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
				mx = q1.back().first, id = q1.back().second;
				q1.pop_back();
			} else {
				mx = q2.back().first, id = q2.back().second;
				q2.pop_back();
			}
			pair<int, int> now = make_pair(mx - mn, id);
			if (q1.empty() || now < q1.front()) {//如果新蛇会变成所有蛇里面最弱的
				ans = q1.size() + q2.size() + 2;//现在有这些蛇，序列里的蛇+取出来的最弱蛇和最强蛇
				int cnt = 0;//当前是奇数轮还是偶数轮
				while (1) {
					cnt++;
					if (q1.size() + q2.size() + 1 == 2) {//该轮(最大蛇吃最小蛇)后，如果只有两条蛇了
						//说明枚举情况到头了
						if (cnt % 2 == 0) ans--;
						//如果最后是偶数个，那么第一个蛇就可以吃
						/*
						比如是4个蛇（倒着看）
						cnt=1:A B C D
						cnt=2:(D-A) B C 因为 C 不敢吃，所以 D 敢吃 A
						cnt=3:(C - (D-A)) B 所以 C 不敢吃 (D-A)
						cnt=4:显然B会吃掉 (C - (D-A))
						故当cnt为偶数，ans就-1
						*/ 
						break;
					}
					int nmx, nid;
					if (q2.empty() || !q1.empty() && q1.back() > q2.back()) {
						nmx = q1.back().first, nid = q1.back().second;
						q1.pop_back();
					} else {
						nmx = q2.back().first, nid = q2.back().second;
						q2.pop_back();
					}
					now = make_pair(nmx - now.first, nid);
					if ((q1.empty() || q1.front() > now) && (q2.empty() || q2.front() > now)) {
						;//now依然是全局最小值,继续深度判断 
					} else {
						if (cnt % 2 == 0) ans--;
						break;
					}
				}
				break;//可以直接判断到结束了
			} else {
				q2.push_front(now);//在新蛇序列里插入新蛇，从front插入，加入的蛇实力一次比一次小
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}