#include<bits/stdc++.h>
#define int long long
using namespace std;
deque<pair<int,int> >q1,q2,q3;
pair<int,int>mid;
int t,n,a[1000005],k,x,y,cnt,bet,l,midl;
bool ok=1;
main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;
	for(int z=1;z<=t;z++)
	{
		if(z==1)
		{
			cin>>n;
			for(int i=1;i<=n;i++)cin>>a[i];
		}
		else
		{
			cin>>k;
			for(int i=1;i<=k;i++)
			{
				cin>>x>>y;
				a[x]=y;
			}
		}
		while(!q1.empty())q1.pop_front();
		while(!q2.empty())q2.pop_front();
		while(!q3.empty())q3.pop_front();
		bet=0;
		ok=1;
		l=n;
		for(int i=1;i<=n;i++)q1.push_back(make_pair(a[i],i));
		while(ok)
		{
			ok=0;
			if(q1.empty())
			{
				l=1;
				break;
			}
			mid=q1.front();
			q1.pop_front();
			if(q1.empty())break;
			if((q2.empty() or q1.back()>q2.back()) and q1.back()>make_pair(mid.first+q1.front().first,q1.front().second))
			{
				ok=1;
				l--;
				q2.push_front({q1.back().first-mid.first,q1.back().second});
				q1.pop_back();
				continue;
			}
			if(!q2.empty() and q2.back()>make_pair(mid.first+q1.front().first,q1.front().second))
			{
				ok=1;
				l--;
				q2.push_front({q2.back().first-mid.first,q2.back().second});
				q2.pop_back();
			}
		}
		q3.push_back(mid);
		ok=1;
		while(!q1.empty() or !q2.empty())
		{
			if(q2.empty())
			{
				q3.push_back(q1.front());
				q1.pop_front();
				continue;
			}
			if(q1.empty())
			{
				q3.push_back(q2.front());
				q2.pop_front();
				continue;
			}
			if(q1.front()<q2.front())
			{
				q3.push_back(q1.front());
				q1.pop_front();
				continue;
			}
			if(q2.front()<q1.front())
			{
				q3.push_back(q2.front());
				q2.pop_front();
			}
		}
		if(l<=2)
		{
			cout<<1<<endl;
			continue;
		}
		while(ok)
		{
			mid=q3.front();
			q3.pop_front();
			if(l==2 or q3.back()>make_pair(mid.first+q3.front().first,q3.front().second))break;
			l--;
			bet++;
		}
		if(!(bet&1) and bet)l--;
		cout<<l+bet<<endl;
	}
	return 0;
}