#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 400500;
const int M = 800500;
int n,m;
int xu[N];
bool can[N];
int lisan[N];
int vx[N];
int ever[N];
int last[N];
struct Info
{
    int a,b,c;
}info[N];
struct Que
{
    int x;
    int l,r;
    int num;
}que[M];
int tree[N];
int qz[N];
int sc[N];
int cc;
int getint()
{
    int res=0;
    char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-')
        ch=getchar();
    bool fan=0;
    if(ch=='-')
    {
        fan=1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    if(fan)
        res=-res;
    return res;
}
int Erfen(int x)
{
    int l=1,r=lisan[0];
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(lisan[mid]==x)
            return mid;
        if(lisan[mid]<x)
            l=mid+1;
        else
            r=mid-1;
    }
}
int cmpx(Info x,Info y)
{
    if(x.a<y.a)
        return 1;
    if(x.a>y.a)
        return -1;
    if(x.b<y.b)
        return 1;
    if(x.b>y.b)
        return -1;
    if(x.c<y.c)
        return 1;
    if(x.c>y.c)
        return -1;
    return 0;
}
bool cmp(Info x,Info y)
{
    return(cmpx(x,y)>=0);
}
int Ef(Info x)
{
    int l=1,r=cc;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int now=cmpx(x,info[mid]);
        if(now==0)
            return mid;
        if(now==1)
            r=mid-1;
        else
            l=mid+1;
    }
}
bool cmx(Que x,Que y)
{
    return(x.x<y.x);
}
void Add(int x)
{
    while(x<=n)
    {
        tree[x]++;
        x+=(x&(-x));
    }
}
int Find(int x)
{
    int res=0;
    while(x)
    {
        res+=tree[x];
        x-=(x&(-x));
    }
    return res;
}
void f()
{
    int i;
    n=getint();
    for(i=1;i<=n;i++)
        lisan[i]=xu[i]=getint();
    sort(lisan+1,lisan+n+1);
    lisan[0]=0;
    for(i=1;i<=n;i++)
    {
        lisan[++lisan[0]]=lisan[i];
        while(i<n && lisan[i]==lisan[i+1])
            i++;
    }
    for(i=1;i<=n;i++)
        xu[i]=Erfen(xu[i]);
    n-=2;
    cc=0;
    memset(can,0,sizeof can);
    for(i=1;i<=n;i++)
    {
        if(xu[i]<=xu[i+1] && xu[i+1]<=xu[i+2])
        {
            can[i]=1;
            cc++;
            info[cc].a=xu[i];
            info[cc].b=xu[i+1];
            info[cc].c=xu[i+2];
        }
    }
    sort(info+1,info+cc+1,cmp);
    int tot=cc;
    cc=0;
    for(i=1;i<=tot;i++)
    {
        info[++cc]=info[i];
        while(i<tot && cmp(info[i],info[i+1])==0)
            i++;
    }
    for(i=1;i<=n;i++)
    {
        if(can[i])
        {
            Info now;
            now.a=xu[i];
            now.b=xu[i+1];
            now.c=xu[i+2];
            vx[i]=Ef(now);
        }
    }
    memset(ever,0,sizeof ever);
    memset(last,0,sizeof last);
    for(i=1;i<=n;i++)
    {
        if(can[i])
        {
            last[i]=ever[vx[i]];
            ever[vx[i]]=i;
        }
    }
    qz[0]=0;
    for(i=1;i<=n;i++)
    {
        qz[i]=qz[i-1];
        if(can[i])
            qz[i]++;
    }
    cc=0;
    m=getint();
    for(i=1;i<=m;i++)
    {
        int l=getint();
        int r=getint()-2;
        if(l>r || r>n)
        {
            sc[i]=0;
            continue;
        }
        cc++;
        que[cc].num=i;
        que[cc].l=l;
        que[cc].r=r;
        que[cc].x=r;
        sc[i]=qz[r]-qz[l-1];
    }
    sort(que+1,que+cc+1,cmx);
    memset(tree,0,sizeof tree);
    int point=0;
    for(i=1;i<=cc;i++)
    {
        while(point<que[i].x)
        {
            point++;
            if(last[point])
                Add(last[point]);
        }
        int now=Find(que[i].r)-Find(que[i].l-1);
        sc[que[i].num]-=now;
    }
    for(i=1;i<=m;i++)
        printf("%d\n",sc[i]);
}
int main()
{
    int t=getint();
    while(t--)
        f();
    return 0;
}