#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++;
}
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=360;
int n,m,K;
int pos[N],l[N],r[N],a[N];
int ql[N],qr[N],qid[N];
int s[N],ss[N],S[N];
void put(int x,int val){
    while(x<=n){
        s[x]+=val;
        x+=lowbit(x);
    }
}
int ask(int x){
    int val=0;
    while(x){
        val+=s[x];
        x-=lowbit(x);
    }return val;
}
ll ans[N];
int main(){
    n=read(),m=read();
    for(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(int i=1;i<=m;i++){
        int p=read();
        while(p--){
            K++;
            ql[K]=read(),qr[K]=read(),qid[K]=i;
        }
    }
    for(int L=1,R=B;L<=n;L+=B,R+=B){
        for(int i=L;i<=R;i++)s[a[i]]++;
        for(int i=1;i<=n;i++)ss[i]=s[i]+ss[i-1];
        for(int i=1;i<=n;i++){
            S[i]=S[i-1];
            if(i<L)S[i]+=R-L+1-ss[a[i]];
            if(i>R)S[i]+=ss[a[i]];
        }
        for(int i=1,j=1;i<=K;i=j){
            bool flag=0;
            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++;
            }ans[qid[i]]+=sum*flag;
        }for(int i=L;i<=R;i++)s[a[i]]--;
    }
    for(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(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],1);
                for(int k=l[pos[qr[j]+1]];k<=qr[j];k++)put(a[k],1);
            }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],1);
            }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++)put(a[k],-1);
                for(int k=l[pos[qr[i]+1]];k<=qr[i];k++)put(a[k],-1);
            }else for(int k=ql[i];k<=qr[i];k++)put(a[k],-1);
            i++;
        }
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
}