#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define ll int
const int N=1e6+5;

ll a[N],n,m;
ll hea[N],nex[N];

ll rt[N],ls[N<<5],rs[N<<5],sum[N<<5],cnt=0;
void insert(ll &p,ll pre,ll l,ll r,ll x){
	p=++cnt;ls[p]=ls[pre];rs[p]=rs[pre];sum[p]=sum[pre]+1;
	if(l==r) return;
	ll mid=l+r>>1;
	if(x<=mid) insert(ls[p],ls[pre],l,mid,x);
	else insert(rs[p],rs[pre],mid+1,r,x);
}
ll query(ll now,ll pre,ll l,ll r,ll x){
	if(l==r&&l<=x) return sum[now]-sum[pre];//找到答案 
	if(l==r) return 0;
	ll mid=l+r>>1;
	ll v=sum[ls[now]]-sum[ls[pre]];
	if(x<=mid) return query(ls[now],ls[pre],l,mid,x);
	else return query(rs[now],rs[pre],mid+1,r,x)+v;
}

int main(){
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(ri i=1;i<=n;i++){
		cin>>a[i];
	}
	for(ri i=1;i<=n;i++){
		nex[i]=hea[a[i]];
		hea[a[i]]=i;
	}
	for(ri i=1;i<=n;i++){
		insert(rt[i],rt[i-1],0,n,nex[i]);
	}
	cin>>m;
	while(m--){
		ll l,r;
		cin>>l>>r;
		cout<<query(rt[r],rt[l-1],0,n,l-1)<<endl;
	}
}

求优化，最近练主席树，虽然离线水过去了