#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],cnt[N],ans[N],from[N];
int n,m,mx;
struct node{
	int l,r,time;
	bool operator<(const node &x)const{
		if(l/mx!=x.l/mx)
			return l<x.l;
		return (l/mx)&1?r<x.r:r>x.r;
	}
}que[N];
set <int> st;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void add(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]==1)
		st.insert(a[x]);
}
void del(int x){
	cnt[a[x]]--;
	if(cnt[a[x]]==0)
		st.erase(a[x]);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	int ls=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
 	if(!from[a[i]])
		from[a[i]]=++ls;
	a[i]=from[a[i]];
}

	m=read();
	for(int i=1;i<=m;i++){
		que[i].l=read();
		que[i].r=read();
		que[i].time=i;
	}
	mx=n/sqrt(m);
	sort(que+1,que+1+m);
	int ll=1,rr=0;
	for(int i=1;i<=m;i++){
		if(que[i].l==que[i].r)
			ans[que[i].time]=1;
		while(ll>que[i].l)
			add(--ll);
		while(rr<que[i].r)
			add(++rr);
		while(ll<que[i].l)
			del(ll++);
		while(rr>que[i].r)
			del(rr--);
		ans[que[i].time]=st.size();
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}