#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 L=1,R=B;L<=n;L+=B,R+=B){
        if(R>n)R=n;
        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=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;i<=m;++i)printf("%lld\n",ans[i]);
}