#include<bits/stdc++.h>
using namespace std;
const int S=1000010;
int n,m,len;
int w[S],ans[S];
int rr[S];
int cnt[S];
struct Q{
	int id,l,r;
}q[S];
inline int get(int x){
	if(rr[x])return rr[x];
	return rr[x]=x/len;
}
inline bool cmp(Q a,Q b){
	int k=get(a.l);
	if(k==get(b.l))return (a.r<b.r)^(k%2);
	else return a.l<b.l;
}
int res;
inline void add(int x){
	if(!cnt[x])res++;
	cnt[x]++;
}
inline void del(int x){
	cnt[x]--;
	if(!cnt[x])res--; 
}
inline int read(){
	int x=0;
	char c=getchar_unlocked();
	while(c<'0'||c>'9')c=getchar_unlocked();
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar_unlocked();
	}
	return x;
}
int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	n=read();
	for(register int i=1;i<=n;i++)w[i]=read();
	m=read();
	len=max(1,(int)(sqrt((long double)(n)*n/(long double)(m))));
	for(register int i=0;i<m;i++){
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q,q+m,cmp);
	int i=0,j=1;
	for(register int k=0;k<m;k++){
		int id=q[k].id,l=q[k].l,r=q[k].r;
		while(i<r)add(w[++i]);
		while(i>r)del(w[i--]);
		while(j<l)del(w[j++]);
		while(j>l)add(w[--j]);
		ans[id]=res;
	}
	for(register int i=0;i<m;i++)cout<<ans[i]<<endl;
}