#include<bits/stdc++.h>
using namespace std;
int n,a[1200010],nxt[1200010],snxt[1200010],q,l,r,block[1200001],num;
map<int,int>mp;
inline long long query(int lef,int rig){
	long long res=0;
	for(int i=lef;i<=min(rig,block[lef]*num);i++){
		if(nxt[i]<lef)res++;
	}
	if(block[lef]!=block[rig]){
		for(int i=(block[rig]-1)*num+1;i<=rig;i++){
			if(nxt[i]<lef)res++;
		}
	}
	for(int i=block[lef]+1;i<block[rig];i++){
		int ll=(i-1)*num+1,rr=i*num;
		while(ll<=rr){
			int mid=ll+rr>>1;
			if(snxt[mid]<lef){
				ll=mid+1;
			}
			else{
				rr=mid-1;
			}
		}
		ll--;
		res+=ll-(i-1)*num;
	}
	return res;
}
int main(){
	cin>>n;num=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		block[i]=(i-1)/num+1;
		if(mp[a[i]]){
			nxt[i]=mp[a[i]];
			snxt[i]=nxt[i];
		}
		mp[a[i]]=i;
	}
	for(int i=1;i<=block[n];i++){
		sort(snxt+(i-1)*num+1,snxt+min(n,i*num)+1);
	}
	cin>>q;
	while(q--){
		cin>>l>>r;
		cout<<query(l,r)<<endl;
	}//O(m*log(n)*sqrt(log(n)))
}