#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define pII pair<int,int>
using namespace std;
const int N=5e5+5,B=555;
int n,m,Cnt,A[N],RS[N],St[N];
LL Ans[N],S[N];
struct Line{int L,R;}Qry[N],F[N/B+5];
inline int Rd()
{
	int S=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while('0'<=c&&c<='9')S=S*10+c-'0',c=getchar();
	return S;
}
int Ch[N];
#define LB(x) ((x)&(-x))
struct BIT
{
	uLL B[N];int t[N],n;
	inline void upd(int x)
	{
		Ch[++Ch[0]]=x;
		B[x>>6]|=1ull<<(x&63),x>>=6,x++;
		while(x<=n)t[x]++,x+=LB(x);
	}
	inline void cl(int x)
	{
		B[x>>=6]=0,x++;
		while(x<=n&&t[x])t[x]=0,x+=LB(x);
	}
	inline int qry(int x)
	{
		int S=__builtin_popcountll(B[x>>6]&(((x&63)==63?0:(1ull<<((x&63)+1)))-1));x>>=6;
		while(x)S+=t[x],x-=LB(x);
		return S;
	}
	inline LL Qry(int L,int R)
	{
		LL S=0;
		for(int i=L;i<=R;i++)S+=qry(A[i]-1);
		return S;
	}
	inline void Upd(int L,int R)
	{
		for(int i=L;i<=R;i++)upd(A[i]);
	}
	inline void Clear()
	{
		for(int i=1;i<=Ch[0];i++)cl(Ch[i]);
		Ch[0]=0;
	}
}T;
#define In(x) ((x-1)/B+1)
int main()
{
	n=Rd(),m=Rd();T.n=(n>>6)+1;
	for(int i=1;i<=In(n);i++)F[i]={F[i-1].R+1,min(i*B,n)};
	for(int i=1;i<=n;i++)A[i]=Rd();
	for(int i=1;i<=m;i++)
	{
		int t=Rd();St[i]=Cnt+1;
		for(int j=0,L,R;j<t;j++)
		{
			L=Rd(),R=Rd(),Qry[++Cnt]={L,R};
			int BL=In(L),BR=In(R);
			if(BL==BR)
			{
				if(R<F[BL].R||L>F[BL].L)Ans[i]+=T.Qry(L,R),T.Upd(L,R);
			}
			else
			{
				if(L>F[BL].L)Ans[i]+=T.Qry(L,F[BL].R);
				if(R<F[BR].R)Ans[i]+=T.Qry(F[BR].L,R);
				if(L>F[BL].L)T.Upd(L,F[BL].R);
				if(R<F[BR].R)T.Upd(F[BR].L,R);
			}
		}
		T.Clear();
	}
	St[m+1]=Cnt+1;
	for(int i=1;i<=In(n);i++)
	{
		for(int j=F[i].L;j<=F[i].R;j++)RS[A[j]]++;
		for(int j=1;j<=n;j++)RS[j]+=RS[j-1];
		int Len=F[i].R-F[i].L+1;
		for(int j=1;j<F[i].L;j++)S[j]=S[j-1]+Len-RS[A[j]];
		for(int j=F[i].L;j<=F[i].R;j++)S[j]=S[j-1];
		for(int j=F[i].R+1;j<=n;j++)S[j]=S[j-1]+RS[A[j]-1];
		for(int j=1;j<=n;j++)RS[j]=0;
		for(int j=1;j<=m;j++)
		{
			int f=0;LL Sum=0;
			for(int k=St[j];k<St[j+1];k++)
			{
				Line v=Qry[k];
				if(v.L<=F[i].L&&F[i].R<=v.R){f=1;continue;}
				if(v.R<=F[i].L)Sum+=S[v.R]-S[v.L-1];
				else
				{
					int L=v.L,R=v.R,BL=In(L),BR=In(R);
					if(BL==BR)
					{
						if(R<F[BL].R||L>F[BL].L)Sum+=S[R]-S[L-1];
					}
					else
					{
						if(L>F[BL].L)Sum+=S[F[BL].R]-S[L-1];
						if(R<F[BR].R)Sum+=S[R]-S[F[BR].L-1];
					}
				}
			}
			Ans[j]+=Sum*f;
		}
	}
	for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
}