#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int t,n,m,a[N];
bool flg;
struct cxk{
	int x,id;
	bool operator >(cxk hs)const{
		if(x==hs.x)return id>hs.id;
		return x>hs.x;
	}
	bool operator <(cxk hs)const{
		if(x==hs.x)return id<hs.id;
		return x<hs.x;
	}
};
deque<cxk> q1,q2,qq;
bool geteating(int last){
	if(last==1)return 0;
	if(last==2)return 1;
    cxk lj=qq.front(),nb=qq.back();
    qq.pop_front(),qq.pop_back();
    cxk n_nb={nb.x-lj.x,nb.id};
    if(qq.empty()||qq.front()<n_nb)return 1;
	qq.push_front(n_nb);
	return !geteating(last-1);
}
int main(){
	scanf("%d",&t);
	while(t--){
		if(!flg){
			scanf("%d",&n);
			for(int i=1;i<=n;++i)scanf("%d",&a[i]);
			flg=1;
		}else{
			scanf("%d",&m);
			while(m--){
				int x,y;
				scanf("%d%d",&x,&y);
				a[x]=y;
			}
		}
        q1.clear(),q2.clear(),qq.clear();
        for(int i=1;i<=n;++i)q1.push_back({a[i],i});
        int ans=n;
        while(ans>1){
        	cxk nb,lj;
    		lj=q1.front(),q1.pop_front();
        	if(q2.empty()||!q1.empty()&&q1.back()>q2.back())nb=q1.back(),q1.pop_back();
        	else nb=q2.back(),q2.pop_back();
        	cxk n_nb={nb.x-lj.x,nb.id};
        	if(!q1.empty()&&n_nb>q1.front())q2.push_front(n_nb),--ans;
        	else{
        		q1.push_front(n_nb);
        		while(!q1.empty()&&!q2.empty())
					if(q1.front()<q2.front())qq.push_back(q1.front()),q1.pop_front();
					else qq.push_back(q2.front()),q2.pop_front();
				while(!q1.empty())qq.push_back(q1.front()),q1.pop_front();
				while(!q2.empty())qq.push_back(q2.front()),q2.pop_front();
				if(!geteating(ans-1))--ans;
				break;
			}
		}
        printf("%d\n",ans);
	}
}