#include<bits/stdc++.h>
#define hor(i,l,r) for(int i=l;i<=r;i++)
#define lor(i,l,r) for(int i=l;i>=r;i--)
#define un unsigned
#define fr front
#define se second
#define fi first
#define pb push_back
using namespace std;
template<typename T> inline void read(T &x){
	x=0;char c=getchar();bool flag=false;
	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	if(flag)x=-x;
}
template<typename T> inline void write(T x){
   	short st[30],tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
}
#define wr write
#define rd read
#define pk putchar(' ')
#define ed puts("")
bitset<100010>Ans[40001],u,vis; 
int l,r,a[1000010],len[1000010],b[1000010],mp[1000010],bl,n,m,cnts[1000010];
struct node{
	int l,r,id;
}qs[1000010];
bool cmp(node a,node b){
	if((a.l-1)/bl==(b.l-1)/bl) return a.r<b.r;
	return a.l<b.l;
}
void add(int p)
{
	u[p+(mp[p]++)]=1;
}
void del(int p)
{
	u[p+(--mp[p])]=0;
}
void solve(int ll,int rr){
	if(ll>rr) return;
	u.reset();
	vis.reset();
	memset(mp,0,sizeof(mp));
	sort(qs+ll*3-2,qs+rr*3+1,cmp);
	for(int i=ll;i<=rr;i++) Ans[i-ll].reset();
	l=r=1;
	add(1);
	for(int i=ll*3-2;i<=rr*3;i++){
		while(r<qs[i].r) add(a[++r]);
		while(r>qs[i].r) del(a[r--]);
		while(l>qs[i].l) add(a[--l]);
		while(l<qs[i].l) del(a[l++]);
		vis[qs[i].id-ll]?Ans[qs[i].id-ll]&=u:(Ans[qs[i].id-ll]=u);
		vis[qs[i].id-ll]=1;
	}
	hor(i,ll,rr) cnts[i]=3*(Ans[i-ll].count());
	return;
}
signed main(){
	rd(n),rd(m);
	bl=sqrt(n);
	hor(i,1,n) rd(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	hor(i,1,n) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	hor(i,1,m) rd(qs[i*3-2].l),rd(qs[i*3-2].r),rd(qs[i*3-1].l),rd(qs[i*3-1].r),rd(qs[i*3].l),rd(qs[i*3].r);
	hor(i,1,m) qs[i*3-2].id=qs[i*3-1].id=qs[i*3].id=i,len[i]=qs[i*3-2].r+qs[i*3-1].r+qs[i*3].r-qs[i*3-2].l-qs[i*3-1].l-qs[i*3].l+3;
	solve(1,m/3),solve(m/3+1,2*m/3),solve(2*m/3+1,m);
	hor(i,1,m) wr(len[i]-cnts[i]),ed;
	return 0;
}