#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REPG(i,h,x) for(int i=h[x];~i;i=edge[i].next)
#define CLR(a,x) memset(a,x,sizeof(a))
#define pii pair<int,int>
const int INF=0x3f3f3f3f;

/*

1类 n^0.75*n^0.75

2类X n^0.75*n^0.5

2类Y n^0.5*n^0.75

3类 n^0.5*n^0.5

剩下的暴力

*/
const int N=1e5+5,M=5e5+5,B1=30,B2=320;
int n,q,S,S1,S2,S3,a[N],lsh[N],pos[N],pre[N],nxt[N],buc[N],bcnt,bcnt1,bcnt2,bel[N],bel1[N],bel2[N],st1[B1],st2[B2],sumB1[B1][B1],sumB2X[B1][B2],sumB2Y[B2][B1],sumB3[B2][B2],sum[N];
ll ans[M];
struct ask{int l,r,id;}Q[M];
struct ask1{int l,r,id,k;};
vector<ask1> Q1[N],Q2[N];
inline void add(int x,int y,int v){
	for(int i=1;i<=bel1[x]-1;i++)
		for(int j=1;j<=bel1[y]-1;j++) sumB1[i][j]+=v;
	for(int i=1;i<=bel1[x]-1;i++)
		for(int j=bel2[st1[bel1[y]]];j<=bel2[y]-1;j++) sumB2X[i][j]+=v;
	for(int i=bel2[st1[bel1[x]]];i<=bel2[x]-1;i++)
		for(int j=1;j<=bel1[y]-1;j++) sumB2Y[i][j]+=v;
	for(int i=bel2[st1[bel1[x]]];i<=bel2[x]-1;i++)
		for(int j=bel2[st1[bel1[y]]];j<=bel2[y]-1;j++) sumB3[i][j]+=v;
	for(int i=st2[bel2[x]];i<=x-1;i++)
		if(lsh[i]<st2[bel2[y]]) sum[i]+=v;
	for(int i=st2[bel2[y]];i<=y-1;i++)
		if(pos[i]<x) sum[pos[i]]+=v;
}
inline int query(int x,int y){return sumB1[bel1[x]][bel1[y]]+sumB2X[bel1[x]][bel2[y]]+sumB2Y[bel2[x]][bel1[y]]+sumB3[bel2[x]][bel2[y]]+sum[x];}
inline void solve(bool typ){
	CLR(sumB1,0),CLR(sumB2X,0),CLR(sumB2Y,0),CLR(sumB3,0),CLR(sum,0),CLR(buc,0);
	for(int i=1;i<=n;i++) buc[a[i]]++;
	for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
	for(int i=1;i<=n;i++) pos[lsh[i]=buc[a[i]]--]=i;
	CLR(buc,0);
	for(int i=1;i<=n;i++) pre[i]=buc[a[i]],buc[a[i]]=i;
	CLR(buc,0);
	for(int i=n;i>=1;i--) nxt[i]=buc[a[i]],buc[a[i]]=i;
	for(int i=1;i<=n;i++){
		add(i,lsh[i],1);
		if(pre[i]) add(pre[i],lsh[pre[i]],-1);
		for(auto j:(typ?Q2[i]:Q1[i]))
			for(int k=j.l;k<=j.r;k++){
				ans[j.id]+=(ll)j.k*query(k,lsh[k]);
				if(nxt[k]<i) ans[j.id]-=(ll)j.k*query(nxt[k],lsh[nxt[k]]);
			}
	} 
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%d",&n);
	S3=pow(n,0.25)+1,S2=S3*S3,S1=S2*S3,bcnt1=(n-1)/S1+1,bcnt2=(n-1)/S2+1;
	for(int i=1;i<=bcnt1;i++){
		st1[i]=(i-1)*S1+1;int ed=(i==bcnt1?n:i*S1);
		for(int j=st1[i];j<=ed;j++) bel1[j]=i;
	}
	for(int i=1;i<=bcnt2;i++){
		st2[i]=(i-1)*S2+1;int ed=(i==bcnt2?n:i*S2);
		for(int j=st2[i];j<=ed;j++) bel2[j]=i;
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&q);
	S=n/sqrt(q),bcnt=(n-1)/S+1;
	for(int i=1;i<=bcnt;i++){
		int st=(i-1)*S+1,ed=(i==bcnt?n:i*S);
		for(int j=st;j<=ed;j++) bel[j]=i;
	}
	for(int i=1;i<=q;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+1+q,[](ask a,ask b){
		if(bel[a.l]!=bel[b.l]) return a.l<b.l;
		if(bel[a.l]&1) return a.r<b.r;
		return a.r>b.r;	
	});
	int L=1,R=0;
	for(int i=1;i<=q;i++){
		if(L>Q[i].l) Q1[R].push_back({Q[i].l,L-1,Q[i].id,1}),L=Q[i].l;
		if(R<Q[i].r) Q2[n-L+1].push_back({n-Q[i].r+1,n-R,Q[i].id,1}),R=Q[i].r;
		if(L<Q[i].l) Q1[R].push_back({L,Q[i].l-1,Q[i].id,-1}),L=Q[i].l;
		if(R>Q[i].r) Q2[n-L+1].push_back({n-R+1,n-Q[i].r,Q[i].id,-1}),R=Q[i].r;
	}
	for(int i=1;i<=n;i++) a[i]=n-a[i]+1;
	solve(false);
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++) a[i]=n-a[i]+1;
	solve(true);
	for(int i=1;i<=q;i++) ans[Q[i].id]+=ans[Q[i-1].id];
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}