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

const int maxn=200005;

int pool[(int)5e7];int ps;
inline int *aloc(int x){
    ps+=x;return pool+ps-x;
}
void unit_monge_mult(int *a,int *b,int *r,int n){
    if(n==2){
        if(a[0]==0&&b[0]==0)r[0]=0,r[1]=1;
        else r[0]=1,r[1]=0;
        return;
    }
    if(n==1){r[0]=0;return;}
    int lps=ps;
    int d=n/2;
    int *a1=aloc(d),*a2=aloc(n-d),*b1=aloc(d),*b2=aloc(n-d);
    int *mpa1=aloc(d),*mpa2=aloc(n-d),*mpb1=aloc(d),*mpb2=aloc(n-d);
    int p[2]={0,0};
    for(int i=0;i<n;i++){
        if(a[i]<d)a1[p[0]]=a[i],mpa1[p[0]]=i,p[0]++;
        else a2[p[1]]=a[i]-d,mpa2[p[1]]=i,p[1]++;
    }
    p[0]=p[1]=0;
    for(int i=0;i<n;i++){
        if(b[i]<d)b1[p[0]]=b[i],mpb1[p[0]]=i,p[0]++;
        else b2[p[1]]=b[i]-d,mpb2[p[1]]=i,p[1]++;
    }
    int *c1=aloc(d),*c2=aloc(n-d);
    unit_monge_mult(a1,b1,c1,d),unit_monge_mult(a2,b2,c2,n-d);
    int *cpx=aloc(n),*cpy=aloc(n),*cqx=aloc(n),*cqy=aloc(n);
    for(int i=0;i<d;i++)cpx[mpa1[i]]=mpb1[c1[i]],cpy[mpa1[i]]=0;
    for(int i=0;i<n-d;i++)cpx[mpa2[i]]=mpb2[c2[i]],cpy[mpa2[i]]=1;
    for(int i=0;i<n;i++)r[i]=cpx[i];
    for(int i=0;i<n;i++)cqx[cpx[i]]=i,cqy[cpx[i]]=cpy[i];
    int hi=n,lo=n,his=0,los=0;
    for(int i=0;i<n;i++){
        if(cqy[i]^(cqx[i]>=hi))his--;
        while(hi>0&&his<0){
            hi--;
            if(cpy[hi]^(cpx[hi]>i))his++;
        }
        while(lo>0&&los<=0){
            lo--;
            if(cpy[lo]^(cpx[lo]>=i))los++;
        }
        if(los>0&&hi==lo)r[lo]=i;
        if(cqy[i]^(cqx[i]>=lo))los--;
    }
    ps=lps;
}
void subunit_monge_mult(int*a,int*b,int*c,int n){
    int lps=ps;
    int *za=aloc(n),*zb=aloc(n),*res=aloc(n),*vis=aloc(n),*mpa=aloc(n),*mpb=aloc(n),*rb=aloc(n);
    memset(vis,0,sizeof(int)*n);
    memset(mpa,-1,sizeof(int)*n);
    memset(mpb,-1,sizeof(int)*n);
    memset(rb,-1,sizeof(int)*n);
    int ca=n;
    for(int i=n-1;i>=0;i--)if(a[i]!=-1){
        vis[a[i]]=1;ca--;za[ca]=a[i];mpa[ca]=i;
    }
    for(int i=n-1;i>=0;i--)if(!vis[i])za[--ca]=i;
    memset(vis,-1,sizeof(int)*n);
    for(int i=0;i<n;i++)if(b[i]!=-1)vis[b[i]]=i;
    ca=0;
    for(int i=0;i<n;i++)if(vis[i]!=-1){
        mpb[ca]=i;rb[vis[i]]=ca++;
    }
    for(int i=0;i<n;i++)if(rb[i]==-1)rb[i]=ca++;
    for(int i=0;i<n;i++)zb[rb[i]]=i;
    unit_monge_mult(za,zb,res,n);
    memset(c,-1,sizeof(int)*n);
    for(int i=0;i<n;i++)if(mpa[i]!=-1&&mpb[res[i]]!=-1)c[mpa[i]]=mpb[res[i]];
    ps=lps;
}

void solve(int *p,int *ret,int n){
    if(n==1){ret[0]=-1;return;}
    int lps=ps,d=n/2;
    int *pl=aloc(d),*pr=aloc(n-d);
    for(int i=0;i<d;i++)pl[i]=p[i];
    for(int i=0;i<n-d;i++)pr[i]=p[i+d];
    int *vis=aloc(n);memset(vis,-1,sizeof(int)*n);
    for(int i=0;i<d;i++)vis[pl[i]]=i;
    int *tl=aloc(d),*tr=aloc(n-d),*mpl=aloc(d),*mpr=aloc(n-d);
    int ca=0;
    for(int i=0;i<n;i++)if(vis[i]!=-1)mpl[ca]=i,tl[vis[i]]=ca++;
    ca=0;memset(vis,-1,sizeof(int)*n);
    for(int i=0;i<n-d;i++)vis[pr[i]]=i;
    for(int i=0;i<n;i++)if(vis[i]!=-1)mpr[ca]=i,tr[vis[i]]=ca++;
    int *vl=aloc(d),*vr=aloc(n-d);
    solve(tl,vl,d),solve(tr,vr,n-d);
    int *sl=aloc(n),*sr=aloc(n);
    iota(sl,sl+n,0);iota(sr,sr+n,0);
    for(int i=0;i<d;i++)sl[mpl[i]]=(vl[i]==-1?-1:mpl[vl[i]]);
    for(int i=0;i<n-d;i++)sr[mpr[i]]=(vr[i]==-1?-1:mpr[vr[i]]);
    subunit_monge_mult(sl,sr,ret,n);
    ps=lps;
}
int invp[maxn],res_monge[maxn];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n,q;
        cin>>n>>q;
        vector<int> a(n);
        for(int i=0;i<n;i++)cin>>a[i],--a[i],invp[a[i]]=i;
        solve(invp,res_monge,n);
        vector<int> fwk(n+1),ans(q);
        vector<vector<pair<int,int> > > qry(n+1);
        for(int i=0;i<q;i++){
            int l,r;
            cin>>l>>r;
            --l;
            qry[l].push_back({r,i});
            ans[i]=r-l;
        }
        for(int i=n-1;i>=0;i--){
            if(res_monge[i]!=-1){
                for(int p=res_monge[i]+1;p<=n;p+=p&-p)fwk[p]++;
            }
            for(auto& z:qry[i]){
                int id,c;tie(id,c)=z;
                for(int p=id;p;p-=p&-p)ans[c]-=fwk[p];
            }
        }
        for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
    }
    return 0;
}
