#include <cstdio>
#include <algorithm>
#define blo(x) (x+size-1)/size
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res;
}
inline void write(int X){if(X>9) write(X/10);putchar(X%10+'0');}
int m,n,k,size=2000,ans=0;
int cnt[1000001],qu[1000001],an[1000001];
struct ask{
	int l,r,id;
}a[1000001];
inline bool cmp(ask x,ask y){return (blo(x.l)!=blo(y.l))?(x.l<y.l):((blo(x.l)&1)?(x.r>y.r):(x.r<y.r));}
inline int solve(){
    n=read();
	for(register int i=1;i<=n;i++){
		qu[i]=read();
	}
	m=read();
	for(register int i=1;i<=m;i++){
		a[i].l=read();
		a[i].r=read();
		a[i].id=i;
	}
	std::sort(a+1,a+m+1,cmp);
	register int l=1,r=0;
	for(register int i=1;i<=m;i++){
		while(l>a[i].l){
			ans+=(++cnt[qu[--l]]==1);
		}
		while(r<a[i].r){
			ans+=(++cnt[qu[++r]]==1);
		}
		while(l<a[i].l){
			ans-=(--cnt[qu[l++]]==0);
		}
		while(r>a[i].r){
			ans-=(--cnt[qu[r--]]==0);
		}
		an[a[i].id]=ans;
	}
	for(register int i=1;i<=m;i++){
		write(an[i]),putchar(10);
	}
}
int main(void) {
	solve();
	return 0;
}

T一个点1.52s 求教qaq