#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int long long
const int N = 1e6+10;
const int INF = 0x3f3f3f3f; 
const int mod = 1e9+7;
#define reg register 
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define Rep(i,j,k) for(int i=j;i>=k;i--)
inline int read(){
	int x = 0,f = 1;
	char ch = getchar();
	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
	while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	return x * f;
}
int a[N];
int T, n, k;
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> T;
    rep(i,1,T){
    	if(i == 1){
    		cin >> n;
			rep(i,1,n){
				cin >> a[i];
			}
		}
		else{
			cin >> k;
			rep(i,1,k){
				int x, y;
				cin >> x >> y;
				a[x] = y;
			}
		}
		deque<pair<int,int>> q1, q2;
		rep(i,1,n){
			q1.push_back({a[i],i});
		}
		int res;
		while(1){
			if(q1.size() + q2.size() == 2){
				res = 1;
				break;
			}
			int x, y, id;
			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();
            }
            auto now = make_pair(x - y, id);
            if (q1.empty() || q1.front() > now) {
                res = q1.size() + q2.size() + 2;
                int cnt = 0;
                while (1) {
                    cnt++;
                    if (q1.size() + q2.size() == 1) {
                        if (cnt % 2 == 0) res--;
                        break;
                    }
                    int x, id;
                    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()))) {
                        if (cnt % 2 == 0) res--;
                        break;
                    } 
                }
                break;
            } 
            else {
                q2.push_front(now);
            }
		}
		cout << res << "\n";
    }
    return 0;
}