rt,代码如下

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int n,m,sz,a[M],bc[M];
int l,r,ans[M],s[M],sum;
struct f{
	int l,r,id;
}a1[M];
bool cmp(f k,f y){
	return bc[k.l]^bc[y.l]?bc[k.l]<bc[y.l]:(bc[k.l]&1)?k.r<y.r:k.r>y.r;
}
void op(int x,int y){
	s[x]+=y;
	if(y>0&&s[x]==1)sum++;
	if(!s[x]&&y<0)sum--;
}
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;
}
int main(){
	n=read();
	sz=sqrt(n);
	for(register int i=1;i<=n;i++){
		a[i]=read();
		bc[i]=(i-1)/sz+1;
	}
	m=read();
	for(register int i=1;i<=m;i++){
		l=read();r=read();
		a1[i].id=i,a1[i].l=l,a1[i].r=r;
	}
	sort(a1+1,a1+m+1,cmp);
	for(register int i=1,l=1,r=0;i<=m;i++){
		while(l<a1[i].l)op(a[l],-1),l++;
		while(l>a1[i].l)l--,op(a[l],1);
		while(r<a1[i].r)r++,op(a[r],1);
		while(r>a1[i].r)op(a[r],-1),r--;
		ans[a1[i].id]=sum;
	}
	for(register int i=1;i<=m;i++){
	    printf("%d",ans[i]);putchar('\n');
	}
	return 0;
}