ref
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int ua, ub, uc, ud, n, m, a[50005], chu[50005], blc, bel[50005], cnt;
ll ans[50005], tmp;
struct Node{
int u, v, idx, val;
}nd[200005];
bool cmp(Node x, Node y){
if(bel[x.u]!=bel[y.u]) return bel[x.u]<bel[y.u];
if(bel[x.u]&1) return x.v>y.v;
else return x.v<y.v;
}
void moqueue(){
int l=1, r=0;
for(int i=1; i<=4*m; i++){
while(l<nd[i].u){
tmp -= 2 * chu[a[l]] - 1;
chu[a[l]]--;
l++;
}
while(l>nd[i].u){
l--;
tmp += 2 * chu[a[l]] + 1;
chu[a[l]]++;
}
while(r<nd[i].v){
r++;
tmp += 2 * chu[a[r]] + 1;
chu[a[r]]++;
}
while(r>nd[i].v){
tmp -= 2 * chu[a[r]] - 1;
chu[a[r]]--;
r--;
}
ans[nd[i].idx] += tmp * nd[i].val;
}
}
void add(int a, int b, int c, int d){
nd[++cnt].u = min(a, b) + 1;
nd[cnt].v = max(a, b);
nd[cnt].idx = c;
nd[cnt].val = d;
}
int main(){
cin>>n;
blc = sqrt(n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
bel[i] = (i - 1) / blc + 1;
}
cin>>m;
for(int i=1; i<=m; i++){
scanf("%d %d %d %d", &ua, &ub, &uc, &ud);
ua--; uc--;
add(ud, ua, i, 1);
add(uc, ub, i, 1);
add(ud, ub, i, -1);
add(ua, uc, i, -1);
}
sort(nd+1, nd+1+4*m, cmp);
moqueue();
for(int i=1; i<=m; i++)
printf("%lld
", ans[i]/2);
return 0;
}