#include<cstdio>
#define ll long long
#define lowbit(x) (x&(-x))
int read(){
    int num=0;
    char ch;ch=getchar();
    while(ch<48||ch>57)ch=getchar();
    while(ch>47&&ch<58){
        num=(num<<1)+(num<<3)+(ch^48);
        ch=getchar();
    }return num;
}
const int N=5e5+15;
int n,m,K,B=3160*4;
int pos[N],l[N],r[N];
int a[N];
int ql[N],qr[N],qid[N];
int s[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();
        pos[i]=(i-1)/B;
        if(!l[pos[i]])l[pos[i]]=i;
        r[pos[i]]=i;
    }
    pos[n+1]=n/B;
    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();
        for(int j=1;j<=p;j++){
            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++)s[i]+=s[i-1];
        for(int i=1;i<=n;i++){
            S[i]=S[i-1];
            if(i<L)S[i]+=R-L+1-s[a[i]];
            if(i>R)S[i]+=s[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[i]+1]]>r[pos[ql[j]-1]])sum-=S[l[pos[qr[i]+1]]-1]-S[r[pos[ql[j]-1]]];
                    sum+=S[qr[j]]-S[ql[j]-1];
                }j++;
            }if(flag)ans[qid[i]]+=sum;
        }
        for(int i=n;i;i--)s[i]-=s[i-1];
        for(int i=L;i<=R;i++)s[a[i]]--;
    }
    for(int i=1,j;i<=K;){
        j=i;
        while(j<=K&&qid[j]==qid[i]){
            if(r[pos[ql[j]-1]]<l[pos[qr[i]+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[i]+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[i]+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[j]-1]]<l[pos[qr[i]+1]]){
                for(int k=ql[i];k<=r[pos[ql[j]-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]);
}