#include<bits/stdc++.h>
using namespace std;
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[205];
	#define gc() (p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++)
	#define flush() (fwrite(b,1,t-b,stdout),t=b)
	#define pc(x) (*t++=x,(t-b==sz)?flush():nullptr)
//	#define gc() (getchar())
//	#define flush() (1)
//	#define pc(x) (putchar(x))
	template<class T> inline void read(T &x){
		x=0; char c=gc(),fushu=0;
		while(!isdigit(c)){if(c=='-')fushu=1; c=gc();}
		while(isdigit(c))x=x*10+(c^48),c=gc();
		if(fushu) x=-x;
	}
	inline void read(char &x){
		x=gc();
		while(!isgraph(x))x=gc();
	}
	inline void read(char *x){
		char c=gc();
		while(!isgraph(c))c=gc();
		while(isgraph(c))*x++=c,c=gc();
		*x='\0';
	}
	inline void read(string &x){
		x=""; char c=gc();
		while(!isgraph(c))c=gc();
		while(isgraph(c))x.push_back(c),c=gc();
	}
	template <typename T,typename ...Args> inline void read(T &x,Args &...args) { read(x),read(args...); }
	template<class T> inline void write(T x){
		if(x<0)pc('-'),x=-x;
		if(!x)pc('0');
		int l=0;
		while(x)p[++l]=(x%10)^48,x/=10;
		while(l)pc(p[l--]);
	}
	inline void write(char &x){pc(x);}
	inline void write(const char &x){pc(x);}
	inline void write(char *x){while(*x!='\0')pc(*x++);}
	inline void write(const char *x){while(*x!='\0')pc(*x++);}
	inline void write(string &x){for(auto c:x)pc(c);}
	template <typename T,typename ...Args> inline void write(T x,Args ...args) { write(x),write(args...); }
	struct F{~F(){flush();}}f;
	#undef gc
	#undef flush
	#undef pc
};
using IO::read;
using IO::write;
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define frein(name) freopen(name".in","r",stdin)
#define freout(name) freopen(name".out","w",stdout)
#define usefile(name) frein(name),freout(name)
#define fo(i,l,r) for(i=(l);i<=(r);++i)
#define fu(i,l,r) for(i=(l);i<(r);++i)
#define fd(i,r,l) for(i=(r);i>=(l);--i)
#define ll long long
#define ull unsigned long long
#define ld long double
#define it128 __int128
#define pi pair<int,int>
#define pl pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vp vector<pi>
#define mts multiset
#define udm unordered_map
#define prq priority_queue
#define endpos(x) prev(x.end())
#define Front(x) (*x.begin())
#define Back(x) (*endpos(x))
#define Size(x) ((int)x.size())
const int N=5e5+5,B=375;
int n,m,a[N],tong[N];
int blk[N],L[N],R[N],totb;
struct arr {
	pi a,b,c;
};
vector<arr> q[N];
struct BIT {
	#define lowbit(x) (x&(-x))
	int s[N];
	inline void update(int x,int val) {
		while(x<=n) s[x]+=val,x+=lowbit(x);
	}
	inline int query(int x) {
		int _s=0;
		while(x) _s+=s[x],x-=lowbit(x); 
		return _s;
	}
}bit;
int s[N];
ll ans[N];
signed main(){
	read(n,m);
	int i,j,k,len,l,r,bl,br,L1,R1,L2,R2,L3,R3,_,flag;
	fo(i,1,n) read(a[i]);
	for(int l=1,r;l<=n;l=r+1) {
		r=min(l+B-1,n);
		++totb;
		L[totb]=l,R[totb]=r;
		fo(i,l,r) blk[i]=totb;
	}
	fo(i,1,m) {
		read(len);
		fo(j,1,len) {
			read(l,r);
			bl=blk[l],br=blk[r];
			L1=R1=L2=R2=L3=R3=0;
			if(bl==br) L1=l,R1=r;
			else if(bl+1==br) L1=l,R1=R[bl],L3=L[br],R3=r;
			else L1=l,R1=R[bl],L2=R[bl]+1,R2=L[br]-1,L3=L[br],R3=r;
			q[i].pb({{L1,R1},{L2,R2},{L3,R3}});
			fo(k,L1,R1) ans[i]+=bit.query(a[k]-1);
			if(L3) fo(k,L3,R3) ans[i]+=bit.query(a[k]-1);
			fo(k,L1,R1) bit.update(a[k],1);
			if(L3) fo(k,L3,R3) bit.update(a[k],1);
		}
	}
	fo(_,1,totb) {
		l=L[_],r=R[_];
		fo(i,1,n) tong[i]=0;
		fo(i,l,r) tong[a[i]]++;
		fo(i,1,n) tong[i]+=tong[i-1];
		fo(i,1,n) {
			s[i]=s[i-1];
			if(l<=i&&i<=r) continue;
			if(i<l) s[i]+=r-l+1-tong[a[i]];
			else s[i]+=tong[a[i]-1];
		}
		fo(i,1,m) {
			flag=0;
			for(auto j:q[i]) if(j.b.fi<=l&&r<=j.b.se) {flag=1; break;}
			if(!flag) continue;
			for(auto j:q[i]) {
				if(j.b.fi<=l&&r<=j.b.se) continue;
				ans[i]+=s[j.a.se]-s[j.a.fi-1];
				if(j.c.fi) ans[i]+=s[j.c.se]-s[j.c.fi-1];
				if(j.b.fi&&j.b.se<l) ans[i]+=s[j.b.se]-s[j.b.fi-1];
			}
		}
	}
	fo(i,1,m) write(ans[i],'\n');
	return 0;
}