#include<iostream>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<cstring>
#include<algorithm>
#define re register int
#define il inline
using namespace std;
const int N=2e5+1000;
const int M=25000;
int blc,n,m,a[N],cnt,Cnt,b[N],sz[N],ans[N];
bitset<N> sum[M+10],now;
bool vis[N];
struct Node{
	int l,r,id;
}q[M*3+10];
template<typename T>il void read(T &x){
	bool f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x=f?(-x):x;
}
il bool cmp(Node a,Node b){
	if(a.l/blc!=b.l/blc)return (a.l/blc)<(b.l/blc);
	a.r<b.r;
}
il void Add(int x){
	sz[a[x]]++;
	now[a[x]+sz[a[x]]-1]=1;
}
il void Del(int x){
	sz[a[x]]--;
	now[a[x]+sz[a[x]]]=0;
} 
il void solve(){
	Cnt=0;
	for(re i=1;i<=M;i++){
		if(cnt==m)break;
		cnt++;
		ans[i]=0;
		vis[i]=0;
		for(re j=1;j<=3;j++){
			Cnt++;
			read(q[Cnt].l);read(q[Cnt].r);
			ans[i]+=q[Cnt].r-q[Cnt].l+1;
			q[Cnt].id=i;
		}
	}
	sort(q+1,q+Cnt+1,cmp);
	int l=1,r=0;
	for(re i=1;i<=Cnt;i++){
		while(r<q[i].r)Add(++r);
		while(l>q[i].l)Add(--l);
		while(l<q[i].l)Del(l++);
		while(r>q[i].r)Del(r--);
		if(vis[q[i].id])sum[q[i].id]&=now;
		else sum[q[i].id]=now;
		vis[q[i].id]=1;
	}
	for(re i=1;i<=Cnt/3;i++)printf("%d\n",ans[i]-3*(int)sum[i].count());
}
int main(){
	read(n);read(m);
	blc=sqrt(n);
	for(re i=1;i<=n;i++){
		read(a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	for(re i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	now.reset();
	solve();
	now.reset();
	memset(sz,0,sizeof(sz));
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	solve();
	now.reset();
	memset(sz,0,sizeof(sz));
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	solve();
	now.reset();
	memset(sz,0,sizeof(sz));
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	solve();
	return 0;
}