rt，我记得这题卡莫队，好像看到有人用莫队过了（？）

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N=1e6+5;
int n,m,a[N],cnt[N],tot,ans[N],fk[N];
struct dat
{
	int id,l,r;
}p[N];
bool cmp(dat a,dat b) {return fk[a.l]^fk[b.l]? fk[a.l]<fk[b.l]: fk[a.l]&1? a.r<b.r: a.r>b.r;}
il void add(re int x) {if(!cnt[a[x]]++) tot++;}
il void del(re int x) {if(!--cnt[a[x]]) tot--;}
#define getchar() (tt==ss&&(tt=(ss=buf)+fread(buf,1,1<<20,stdin),ss==tt)?EOF:*ss++)
char buf[1<<20],*ss=buf,*tt=buf;
il int read()
{
	re int x=0,f=1;re char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
il void write(re int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
int main()
{
	n=read();
	re int t=sqrt(n);
	for(re int i=1;i<=n;i++) a[i]=read(),fk[i]=(i-1)/t+1;
	m=read();
	for(re int i=1;i<=m;i++)
	{
		p[i].l=read(),p[i].r=read();
		p[i].id=i;
	}
	sort(p+1,p+1+m,cmp);
	re int L=0,R=0;
	for(re int i=1;i<=m;i++)
	{
		while(L>p[i].l) add(--L);
		while(R<p[i].r) add(++R);
		while(L<p[i].l) del(L++);
		while(R>p[i].r) del(R--);
		ans[p[i].id]=tot;
	}
	for(re int i=1;i<=m;i++)
		write(ans[i]),putchar('\n');
	return 0;
}