#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5,maxt=1e6+5,maxq=2e5+5;
int n,q,k,len,s,l,r,a[maxn],ans[maxn],t[maxn],cnt[maxt];
struct node{
	int l,r,id;
	inline bool operator <(const node &o) const{
		return t[l]<t[o.l]||(t[l]==t[o.l]&&r<o.r);
	}
}f[maxq];
inline void add(int x){
	if(!cnt[a[x]])
		++s;
	++cnt[a[x]];
	
}
inline void del(int x){
	--cnt[a[x]];
	if(!cnt[a[x]])
		--s;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		f[i].id=i;
		scanf("%d%d",&f[i].l,&f[i].r);
	}
	len=n/sqrt(q);
	for(int i=1;i<=(n+len-1)/len;++i)
		for(int j=(i-1)*len+1;j<=min(n,i*len);++j)
			t[j]=i;
	sort(f+1,f+q+1);
	for(int i=f[1].l;i<=f[1].r;++i){
		if(!cnt[a[i]])
			++s;
		++cnt[a[i]];
	}
	l=f[1].l,r=f[1].r;
	for(int i=1;i<=q;++i){
		while(f[i].l<l) add(--l);
		while(f[i].l>l) del(l++);
		while(f[i].r<r) del(r--);
		while(f[i].r>r) add(++r);
		ans[f[i].id]=s;
	}
	for(int i=1;i<=q;++i)
		printf("%d\n",ans[i]);
	return 0;
}