86pts,TLE,怎么卡都卡不过#9，#10

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
inline void write(register int ans,register bool bk){if(ans<0)putchar('-'),ans=-ans;if(ans==0){if(!bk)putchar('0');return ;}write(ans/10,true);putchar(ans%10^'0');}
inline void qr(register int &ret){register int x=0,f=0;register char ch=getchar();while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();ret=f?-x:x;}
struct node{
	int l,r,id,cl;
}p[MAXN];
inline bool cmp(register node x,register node y){
	return x.cl==y.cl?(x.cl&1?x.r<y.r:x.r>y.r):x.l<y.l;
}
int a[MAXN],cnt[MAXN],ans[MAXN];
int main() {
    register int n,m,s,tot;
	qr(n);
	s=floor(sqrt(n));
	for(register int i=1;i<=n;++i){
		qr(a[i]);
	}
	qr(m);
	for(register int i=1;i<=m;++i){
		qr(p[i].l),qr(p[i].r);
		p[i].cl=(p[i].l+s-1)/s;
		p[i].id=i;
	}
	sort(p+1,p+m+1,cmp);
	register int l=0,r=0;
	for(register int i=1;i<=m;++i){
		while(l>p[i].l) tot+=++cnt[a[--l]]==1;
		while(r<p[i].r) tot+=++cnt[a[++r]]==1;
		while(l<p[i].l) tot-=--cnt[a[l++]]==0;
		while(r>p[i].r) tot-=--cnt[a[r--]]==0;
//		cout << tot << " " << p[i].id << endl;
		ans[p[i].id]=tot;
	}
	for(register int i=1;i<=m;++i){
		write(ans[i],false);
		putchar('\n');
	}
	return 0;
}