#include<bits/stdc++.h>
using namespace std;

const int N=1e5+1e3+7;

int T,n,m;

int a[N],ans[N];

vector<int>v;

struct Query{
	int x,y;
	int id;
}q[N];

bool cmp(Query a,Query b)
{
	return a.x>b.x;
}

int cnt,rt,f[N];

struct T{
	int ls,rs;
	int mn;
}t[N*31];

void update(int x)
{
	t[x].mn=min(t[t[x].ls].mn,t[t[x].rs].mn);
}

void insert(int &x,int l,int r,int p,int val)
{
	if(!x)
		x=++cnt;
	int mid=(l+r)>>1;
	if(l==r)
	{
		t[x].mn=val;
		return;
	}
	if(p<=mid)
		insert(t[x].ls,l,mid,p,val);
	else
		insert(t[x].rs,mid+1,r,p,val);
	update(x);
}

int query(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
		return t[x].mn;
	if(!x)
		return t[x].mn;
	int mid=(l+r)>>1,ret=0x7fffffff;
	if(L<=mid)
		ret=min(ret,query(t[x].ls,l,mid,L,R));
	if(R>mid)
		ret=min(ret,query(t[x].rs,mid+1,r,L,R));
	return ret;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=cnt;i++)
			t[i].mn=t[i].ls=t[i].rs=0;
		cnt=rt=0;
		for(int i=1;i<=n;i++)	
			f[i]=a[i]=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)
			scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i;
		int o=0;
		for(int i=1;i<=n;i++)
			if(a[i]>o)
				o=a[i],v.push_back(i);
		sort(q+1,q+m+1,cmp);
		int j=1;
		t[0].mn=0x7fffffff;
		for(int i=n;i>=1;i--)
		{
			if(q[j].x==i)
			{
				int last=j;
				while(j+1<=m&&q[j+1].x==i)
					j++;
				int pre=lower_bound(v.begin(),v.end(),i)-v.begin()-1;
				for(int k=last;k<=j;k++)
				{
					int c=q[k].y;
					if(pre!=-1&&c<=a[v[pre]])
						ans[q[k].id]=(int)v.size();
					else
					{
						ans[q[k].id]=pre+1+1;
						int suf=query(rt,1,1e9,c+1,1e9);
						if(suf!=0x7fffffff)
							ans[q[k].id]+=f[suf];
					}
				}
				j++;
			}
			int nx=query(rt,1,1e9,a[i]+1,1e9);
			if(nx==0x7fffffff)
				f[i]=1;
			else
				f[i]=f[nx]+1;
			insert(rt,1,1e9,a[i],i);
		}
		for(int i=1;i<=m;i++)
			printf("%d\n",ans[i]);
	}
}
/*
1
5 3
1 2 3 4 4
1 5
5 5
2 3

*/