#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;
int n,m,K,B=720;
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];
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--){
            K++;
            ql[K]=read(),qr[K]=read(),qid[K]=i;
        }
    }
    for(register int L=1,R=B;L<=n;L+=B,R+=B){
        for(register int i=L;i<=R;i++)s[a[i]]++;
        for(register int i=1;i<=n;i++)ss[i]=s[i]+ss[i-1];
        for(register int i=1;i<=n;i++){
            S[i]=S[i-1];
            if(i<L)S[i]+=R-L+1-ss[a[i]];
            else if(i>R)S[i]+=ss[a[i]];
            else --s[a[i]];
        }
        for(register int i=1,j=1;i<=K;i=j){
            register int flag=0;
            register ll sum=0;
            while(j<=K&&qid[j]==qid[i]){
                if(ql[j]<=L&&qr[j]>=R)flag=1;
                else{
                    if(ql[j]>R&&l[pos[qr[j]+1]]>r[pos[ql[j]-1]])sum-=S[l[pos[qr[j]+1]]-1]-S[r[pos[ql[j]-1]]];
                    sum+=S[qr[j]]-S[ql[j]-1];
                }j++;
            }if(flag)ans[qid[i]]+=sum;
        }
    }
    for(register int i=1,j=1;i<=K;){
        while(j<=K&&qid[j]==qid[i]){
            while(j<=K&&qid[j]==qid[i]){
                if(r[pos[ql[j]-1]]<l[pos[qr[j]+1]]){
                    for(int k=ql[j];k<=r[pos[ql[j]-1]];k++)ans[qid[i]]+=ask(a[k]);
                    for(int k=l[pos[qr[j]+1]];k<=qr[j];k++)ans[qid[i]]+=ask(a[k]);
                    for(int k=ql[j];k<=r[pos[ql[j]-1]];k++)put(a[k]);
                    for(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(int k=ql[i];k<=r[pos[ql[i]-1]];k++)clr(a[k]);
                    for(int k=l[pos[qr[i]+1]];k<=qr[i];k++)clr(a[k]);
                }else for(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]);
}