// #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 ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second

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

ll ans[maxn],sum[maxn];

pii qry[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[500005];
        ull b[500005];
        inline void updata(int i,int y){
            mdf[++ctt]=i;
            b[i>>6]|=1ull<<(i&63),i>>=6,i++;
            while(i<=N) ++ts[i],i+=lowbit(i);
        }
        inline void clr(int i){
            b[i>>=6]=0,i++;
            while(i<=N&&ts[i]) ts[i]=0,i+=lowbit(i);
        }
        inline int getsum(int i){
            int res=__builtin_popcountll(b[i>>6]&(((i&63)==63?0:(1ull<<((i&63)+1)))-1));
            i>>=6;
            while(i) res+=ts[i],i-=lowbit(i);
            return res;
        }
}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);}
inline void clr(){for(int i=1;i<=ctt;i++) Ts.clr(mdf[i]);ctt=0;}

int main()
{
    // int st=clock();
    n=read(),m=read();N=(n>>6)+1;
    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]=make_pair(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);
            }
        }
        clr();
    }
    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;
}