#pragma GCC optimize(2,3)
#include<bits/stdc++.h>
using namespace std;

const int maxB=6e3+5,maxn=5e5+5;

#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

int n,m,B,cnt;
int M[maxn],a[maxn],ressum[maxn];

ll ans[maxn],sum[maxn];

pii qry[maxn];

bool vis[maxn];

inline int read()
{
    char c=getchar();int fx=1,sum=0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    if(c=='-') c=getchar(),fx=-1;
    while('0'<=c&&c<='9') sum=(sum<<1)+(sum<<3)+c-'0',c=getchar();
    return sum*fx;
}

struct fknode1{int l,r;}fk[maxB];
class treearray
{
    private:
        #define lowbit(x) (x&(-x))
    public:
        int ts[maxn];
        unsigned long long bt[maxn];
        inline void updata(int x,int y){bt[x>>6]|=1ull<<(x&63),x>>=6,x++;for(;x<=(n>>6)&&x;x+=lowbit(x)) ts[x]+=y;}
        inline int getsum(int x){int sum=__builtin_popcountll(bt[x>>6]&(((x&63)==63?0:(1ull<<((x&63)+1)))-1));for(;x;x-=lowbit(x)) sum+=ts[x];return sum;}
        inline void clr(int x){x>>=6;bt[x]=0;for(;x<=(n>>6)&&x&&ts[x];x+=lowbit(x)) ts[x]=0;}
}Ts;

inline ll add(int l,int r){ll sum=0;for(int i=l;i<=r;i++) sum+=Ts.getsum(a[i]-1);return sum;}
inline void upd(int l,int r){for(int i=l;i<=r;i++) Ts.updata(a[i],1),vis[a[i]]=1;}
inline void clr(int l,int r){for(int i=l;i<=r;i++) if(vis[a[i]]) Ts.clr(a[i]),vis[a[i]]=0;}

int main()
{
    // int st=clock();
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    n=read(),m=read();
    B=300;
    for(int i=1;i<=(n-1)/B+1;i++){fk[i].l=fk[i-1].r+1,fk[i].r=min(fk[i].l+B-1,n);}
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int t=read();M[i]=cnt+1;
        for(int j=0,l,r;j<t;j++)
        {
            l=read(),r=read(),qry[++cnt]={l,r};
            int numl=(l-1)/B+1,numr=(r-1)/B+1;
            if(numl==numr) {if(r<fk[numl].r||l>fk[numl].l) ans[i]+=add(l,r),upd(l,r);}
            else
            {
                if(l>fk[numl].l) ans[i]+=add(l,fk[numl].r);
                if(r<fk[numr].r) ans[i]+=add(fk[numr].l,r);
                if(l>fk[numl].l) upd(l,fk[numl].r);
                if(r<fk[numr].r) upd(fk[numr].l,r);
            }
        }
        for(int j=M[i];j<=cnt;j++)
        {
            pii v=qry[j];
            int l=v.fi,r=v.se;
            int numl=(l-1)/B+1,numr=(r-1)/B+1;
            if(numl==numr) {if(r<fk[numl].r||l>fk[numl].l) clr(l,r);}
            else
            {
                if(l>fk[numl].l) clr(l,fk[numl].r);
                if(r<fk[numr].r) clr(fk[numr].l,r);
            }
        }
    }
    M[m+1]=cnt+1;
    for(int i=1;i<=(n-1)/B+1;i++)
    {
        for(int j=fk[i].l;j<=fk[i].r;j++) ressum[a[j]]++;
        for(int j=1;j<=n;j++) ressum[j]+=ressum[j-1];
        int det=fk[i].r-fk[i].l+1;
        for(int j=1;j<fk[i].l;j++) sum[j]=sum[j-1]+(det-ressum[a[j]]);
        for(int j=fk[i].l;j<=fk[i].r;j++) sum[j]=sum[j-1];
        for(int j=fk[i].r+1;j<=n;j++) sum[j]=sum[j-1]+ressum[a[j]-1];
        for(int j=1;j<=n;j++) ressum[j]=0;
        for(int j=1;j<=m;j++)
        {
            int flg=0;ll res=0;
            for(int k=M[j];k<M[j+1];k++)
            {
                pii v=qry[k];
                if(v.fi<=fk[i].l&&fk[i].r<=v.se) {flg=1;continue;}
                if(v.se<=fk[i].l) res+=sum[v.se]-sum[v.fi-1];
                else
                {
                    int l=v.fi,r=v.se,numl=(l-1)/B+1,numr=(r-1)/B+1;
                    if(numl==numr) {if(r<fk[numl].r||l>fk[numl].l) res+=sum[r]-sum[l-1];}
                    else
                    {
                        if(l>fk[numl].l) res+=sum[fk[numl].r]-sum[l-1];
                        if(r<fk[numr].r) res+=sum[r]-sum[fk[numr].l-1];
                    }
                }
            }
            ans[j]+=res*flg;
        }
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    // cerr<<clock()-st;
}