rt

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int word;
typedef unsigned short hword;
typedef unsigned char byte;
struct READ{
	char c;
	inline READ(){c=getchar();}
	template<typename type>
	inline READ& operator >>(register type& num){
		while('0'>c||c>'9') c=getchar();
		for(num=0;'0'<=c&&c<='9';c=getchar())
			num=num*10+(c-'0');
		return *this;
	}
};
hword num[1<<16],size;
hword countl[1<<16],countr[1<<16];
struct question{
	word l,r,id;
	byte type;
	inline question(){}
	inline void operator()(word a,word b,word ID,word t){
		(l=a<b? a:b),(r=a>b? a:b),id=ID,type=t;
	}
	inline ull operator()(){return (ull)(r)<<32|l;}
}q[1<<18];
inline bool cmp0(const question &q1,const question &q2){
	if(q1.l/size==q2.l/size) return q1.r<q2.r;
	return q1.l/size==q2.l/size;
}
inline bool cmp1(const question &q1,const question &q2){
	if(q1.id==q2.id) return q1.type<q2.type;
	return q1.id<q2.id;
}
int main(){
	register READ cin;
	register word n,m;
	cin>>n,size=sqrt(n);
	for(register word i=1;i<=n;++i) cin>>num[i];
	cin>>m;
	register word l,r,l_,r_,qsize=0;
	for(register word i=1;i<=m;++i){
		cin>>l>>r>>l_>>r_,--l,--l_;
		q[++qsize](l,l_,i,0);
		q[++qsize](r,r_,i,1);
		q[++qsize](l,r_,i,2);
		q[++qsize](r,l_,i,3);
	}
	std::sort(q+1,q+qsize+1,cmp0);
	l=0,r=0;
	register ull ans=1;
	++countl[num[0]],++countr[num[0]];
	for(register word i=1;i<=qsize;++i){
		while(r<q[i].r) ++countr[num[++r]],ans+=countl[num[r]];
		while(q[i].r<r) --countr[num[r--]],ans-=countl[num[r]];
		while(l<q[i].l) ++countl[num[++l]],ans+=countr[num[l]];
		while(q[i].l<l) --countl[num[l--]],ans-=countr[num[l]];
		q[i].l=ans,q[i].r=ans>>32;
	}
	std::sort(q+1,q+qsize+1,cmp1);
	for(register word i=1;i<=qsize;i+=4)
		printf("%llu\n",q[i]()+q[i+1]()-q[i+2]()-q[i+3]());
	return 0;
}