#include<cstdio>
#define ll long long
#define lowbit(x) (x&(-x))
static const int BUF = 1<<20;
inline char gc() {
    static char buf[BUF],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,BUF,stdin),p1==p2)?-1:*p1++;
}
inline int read(){
    int num=0;
    char ch;ch=gc();
    while(ch<48||ch>57)ch=gc();
    while(ch>47&&ch<58){
        num=(num<<1)+(num<<3)+(ch^48);
        ch=gc();
    }return num;
}
const int N=5e5+15;
const int B=400;
int n,m,K;
int pos[N],l[N],r[N];
int a[N];
int ql[N],qr[N],qid[N];
int s[N],S[N],ss[N];
inline void put(register int x){
    while(x<=n){
        ++s[x];
        x+=lowbit(x);
    }
}
inline int ask(register int x){
    int val=0;
    while(x){
        val+=s[x];
        x-=lowbit(x);
    }return val;
}
inline void clr(register int x){
    while(x<=n){
        if(!s[x])return;
        s[x]=0;
        x+=lowbit(x);
    }
}
ll ans[N],sum;
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
        if(i>B)pos[i]=pos[i-B]+1;
        if(!l[pos[i]])l[pos[i]]=i;
        r[pos[i]]=i;
    }
    if(n+1>B)pos[n+1]=pos[n+1-B]+1;
    if(!l[pos[n+1]])l[pos[n+1]]=n+1;
    r[pos[n+1]]=n+1;
    for(register int i=1,p;i<=m;++i){
        p=read();
        while(p--)ql[++K]=read(),qr[K]=read(),qid[K]=i;
    }
    for(register int i=1,j=1;i<=K;){
        while(j<=K&&qid[j]==qid[i]){
            if(r[pos[ql[j]-1]]<l[pos[qr[j]+1]]){
                for(register int k=ql[j];k<=r[pos[ql[j]-1]];++k)ans[qid[i]]+=ask(a[k]);
                for(register int k=l[pos[qr[j]+1]];k<=qr[j];++k)ans[qid[i]]+=ask(a[k]);
                for(register int k=ql[j];k<=r[pos[ql[j]-1]];++k)put(a[k]);
                for(register int k=l[pos[qr[j]+1]];k<=qr[j];++k)put(a[k]);
            }else{
                for(int k=ql[j];k<=qr[j];++k)ans[qid[i]]+=ask(a[k]);
                for(int k=ql[j];k<=qr[j];++k)put(a[k]);
            }j++;
        }
        while(i<j){
            if(r[pos[ql[i]-1]]<l[pos[qr[i]+1]]){
                for(register int k=ql[i];k<=r[pos[ql[i]-1]];++k)clr(a[k]);
                for(register int k=l[pos[qr[i]+1]];k<=qr[i];++k)clr(a[k]);
            }else for(register int k=ql[i];k<=qr[i];++k)clr(a[k]);
            ++i;
        }
    }for(register int i=1;i<=m;++i)printf("%lld\n",ans[i]);
}