#include<bits/stdc++.h>
using namespace std;

const int maxB=165,maxn=5e5+5;

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

struct fknode
{
    int l,r;
}fk[maxB];
class treearray
{
    private:
        #define N 500000
        inline int lowbit(int x){return x&(-x);}
    public:
        int ts[maxn];
        inline void updata(int x,int y){for(;x<=N&&x;x+=lowbit(x)) ts[x]+=y;}
        inline int getsum(int x){int sum=0;for(;x;x-=lowbit(x)) sum+=ts[x];return sum;}
        inline void clr(int x){for(;x<=N&&x;x+=lowbit(x)) ts[x]=0;}
}Ts;

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

ll ans[maxn],sum[maxn];

vector<pii>qry[maxn];

bool vis[maxn];

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()
{
    scanf("%d%d",&n,&m);
    B=sqrt(n/log2(n));
    for(int i=1;i<=(n-1)/B+1;i++)
    {
        fk[i].l=fk[i-1].r+1;
        fk[i].r=fk[i].l+B-1;
    }
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&M[i]);
        for(int j=1,l,r;j<=M[i];j++)
        {
            scanf("%d%d",&l,&r),qry[i].push_back({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(auto v:qry[i])
        {
            int l=v.fi,r=v.se;
            int numl=(l-1)/B+1,numr=(r-1)/B+1;
            if(numl==numr) clr(l,r);
            else
            {
                clr(l,fk[numl].r);
                clr(fk[numr].l,r);
            }
        }
    }
    for(int i=1;i<=(n-1)/B+1;i++)
    {
        upd(fk[i].l,fk[i].r);int det=fk[i].r-fk[i].l+1;
        for(int j=1;j<fk[i].l;j++) sum[j]=sum[j-1]+(det-Ts.getsum(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]+Ts.getsum(a[j]-1);
        clr(fk[i].l,fk[i].r);
        for(int j=1;j<=m;j++)
        {
            int flg=0;ll res=0;
            for(pii v:qry[j])
            {
                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]);
}