RT，60pts，就差一点点

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define RI register int
using namespace std;
const int N=1000005;
struct noda{
	int l,r,id;
}q[N];
int bl[N],a[N],n,m,anss[N],cnt[N],ans,len;
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;
}
inline void write(int x){ 
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
int cmp(noda x,noda y){
	return (bl[x.l]^bl[y.l])?bl[x.l]<bl[y.l]:((bl[x.l]&1)?x.r<y.r:x.r>y.r);
}
int main(){
	n=read();
	for(RI i=1;i<=n;i++) a[i]=read();
	len=ceil((double)sqrt(n));
	for(RI i=1;i<=n;i++){
		bl[i]=(i-1)/len+1;
	}
	m=read();
	for(RI i=1;i<=m;i++){
		q[i].l=read();
		q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	register int l=0,r=0;
	for(RI i=1;i<=m;i++){ 
//		while(l<q[i].l) del(l++);
//		while(l>q[i].l) add(--l);
//		while(r>q[i].r) del(r--);
//		while(r<q[i].r) add(++r);
		while(l>q[i].l) ans+=!(cnt[a[--l]]++);
		while(r<q[i].r) ans+=!(cnt[a[++r]]++);
		while(l<q[i].l) ans-=!(--cnt[a[l++]]);
		while(r>q[i].r) ans-=!(--cnt[a[r--]]);
		anss[q[i].id]=ans;
	}
	for(RI i=1;i<=m;i++){
		write(anss[i]);
		putchar('\n');
	}
	return 0;
}