#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void in(T &x){
	char c=getchar();bool f=0;
	while (c<'0'||c>'9') {
		if (c=='-') f=1;
		c=getchar();
	}
	for (x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+(c&15);
	x=f?-x:x;
}
template<typename T>
inline void out(T x){
	if(x<0) putchar('-'),x=-x;
	if(x/10) out(x/10);
	putchar((x%10)|48);
}
const int N=1e6+5;
int n,m;
int a[N],c[N],ton[N],lst[N];
void updata(int i,int data){
	for(;i<=n;i+=i&-i)
		c[i]+=data;
}
int sum(int i){
	int ans=0;
	for(;i;i-=i&-i)
		ans+=c[i];
	return ans;
}
struct qstn{
	int l,r,id;
};
bool cmp1(const qstn &x,const qstn &y){
	if(x.r==y.r) return x.l<y.l;
	return x.r<y.r;
}
int ans[N];
qstn q[N];
int main(){
	in(n);
	for(register unsigned int i=1;i<=n;i++){
		in(a[i]);
		if(!ton[a[i]]){
			lst[i]=N-5;
			ton[a[i]]=i;
		}else{
			lst[i]=ton[a[i]];
			ton[a[i]]=i;
		}
	}
	in(m);
	for(register unsigned int i=1;i<=m;i++){
		in(q[i].l);
		in(q[i].r);
		q[i].id=i;
	}
	int j=1;
	sort(q+1,q+m+1,cmp1);
	for(register unsigned int i=1;i<=m;i++){
		for(;j<=q[i].r;++j){
			if(lst[j])
				updata(lst[j],-1);
			updata(j,1);
		}
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
	}
	for(register unsigned int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}