#include <iostream>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <deque>
using namespace std;
typedef long long int ll;
const int N=1e6+9,INF=1e9;
const double eps=1e-5;
typedef pair <int,int> PII;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0' && c<='9') {x=x*10+c-48,c=getchar();}
    return x*f;
}
inline ll readll()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0' && c<='9') {x=x*10+c-48,c=getchar();}
    return x*f;
}
int n,a[N],ans;
deque <PII> q1,q2;
int main()
{
    // #define FILEIO
    #ifdef FILEIO
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
    int T=read();
    for(int t=1;t<=T;t++)
    {
        if(t==1)
        {
            n=read();
            for(int i=1;i<=n;i++) a[i]=read();
        }
        else
        {
            int k=read();
            for(int i=1;i<=k;i++)
            {
                int x=read(),y=read();
                a[x]=y;
            }
        }
        q1.clear(),q2.clear();
        for(int i=1;i<=n;i++) q1.push_back({a[i],i});
        while(true)
        {
            if(q1.size()+q2.size()==2)
            {
                ans=1;
                break;
            }
            int x=q1.front().first,y,id;
            q1.pop_front();
            if(q2.empty() || (q1.empty()==false && q1.back()>q2.back()))
                y=q1.back().first,id=q1.back().second,q1.pop_back();
            else y=q2.back().first,id=q2.back().second,q2.pop_back();
            PII p={y-x,id};
            if(q1.empty() || q1.front()>p)
            {
                ans=q1.size()+q2.size()+2;
                int sum=0;
                while(true)
                {
                    sum++;
                    if(q1.size()+q2.size()==1)
                    {
                        if(sum%2==0) ans--;
                        break;
                    }
                    if(q2.empty() || (q1.empty()==false && q1.back()>q2.back()))
                        y=q1.back().first,id=q1.back().second,q1.pop_back();
                    else y=q2.back().first,id=q2.back().second,q2.pop_back();
                    p={y-p.first,id};
                    if((q1.empty() || p<q1.front()) && (q2.empty() || p<q2.front()));
                    else
                    {
                        if(sum%2==0) ans--;
                        break;
                    }
                }
                break;
            }
            else q2.push_front(p);
        }
        cout<<ans<<'\n';
    }
    cerr<<endl<<1e3*clock()/CLOCKS_PER_SEC<<"ms";
    return 0;
}