#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=500050;
const int M=2*N;

int ls[M],rs[M],tsz,root;
int cnt[M][2],lzy_sw[M];
ll sum[M],lzy_add[M][2];

void upd_sw(int c){
	swap(cnt[c][0],cnt[c][1]);
	swap(lzy_add[c][0],lzy_add[c][1]);
	lzy_sw[c]^=1;
}
void upd_add(int c,ll x,ll y){
	sum[c]+=x*cnt[c][0]+y*cnt[c][1];
	lzy_add[c][0]+=x;
	lzy_add[c][1]+=y;
}
void push(int c){
	if(lzy_sw[c]){
		upd_sw(ls[c]);
		upd_sw(rs[c]);
		lzy_sw[c]=0;
	}
	upd_add(ls[c],lzy_add[c][0],lzy_add[c][1]);
	upd_add(rs[c],lzy_add[c][0],lzy_add[c][1]);
	lzy_add[c][0]=0;
	lzy_add[c][1]=0;
}
void pull(int c){
	sum[c]=sum[ls[c]]+sum[rs[c]];
	cnt[c][0]=cnt[ls[c]][0]+cnt[rs[c]][0];
	cnt[c][1]=cnt[ls[c]][1]+cnt[rs[c]][1];
}
void Sw(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return;
	if(qs<=ss&&qe>=se){
		upd_sw(c);
		return;
	}
	int mid=ss+se>>1;
	push(c);
	Sw(ls[c],ss,mid,qs,qe);
	Sw(rs[c],mid+1,se,qs,qe);
	pull(c);
}
void Add(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return;
	if(qs<=ss&&qe>=se){
		upd_add(c,0,1);
		return;
	}
	int mid=ss+se>>1;
	push(c);
	Add(ls[c],ss,mid,qs,qe);
	Add(rs[c],mid+1,se,qs,qe);
	pull(c);
}
ll Get(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return sum[c];
	int mid=ss+se>>1;
	push(c);
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
void Build(int&c,int ss,int se){
	c=++tsz;
	if(ss==se){
		cnt[c][0]=1;
		return;
	}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	pull(c);
}

int a[N];
vector<pair<int,int>> Qs[N];
ll ans[N];
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	int q;
	scanf("%i",&q);
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%i %i",&l,&r);
		Qs[r].pb({i,l});
	}
	Build(root,1,n);
	map<int,int> last;
	for(int i=1;i<=n;i++){
		if(last[a[i]]){
			Sw(root,1,n,1,last[a[i]]);
		}
		Sw(root,1,n,1,i);
		last[a[i]]=i;
		Add(root,1,n,1,i);

		//for(int j=1;j<=n;j++)printf("%lld ",Get(root,1,n,j,j));
		//printf("\n");

		for(auto qu:Qs[i]){
			ans[qu.first]=Get(root,1,n,qu.second,i);
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}