莫队48分求卡常（悬关）

#include<bits/stdc++.h>
using namespace std;
#define rint register int
const int maxn=1e6+5;
inline int read() {
    int x=0;char ch=getchar();bool sign=false;
    while(!isdigit(ch))
        {if(ch=='-')sign=true;ch=getchar();}
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return sign?-x:x;
}
inline void write(int x) {
    if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct question{int l,r,id;}q[maxn];
int n,block,m,a[maxn],pos[maxn],rk[maxn];
int ans[maxn],cnt[maxn],tans;
bool cmp(question i,question j){
	if(pos[i.l]!=pos[j.l])return pos[i.l]<pos[j.l];
	if(pos[i.l]&1)return i.r>j.r;
	return i.r<j.r;
}
int main(){
	n=read();
	for(rint i=1;i<=n;i++)
		a[i]=read(),rk[i]=a[i];
	sort(rk+1,rk+n+1);
	int qaq=unique(rk+1,rk+n+1)-rk-1;
	for(rint i=1;i<=n;i++)
		a[i]=lower_bound(rk+1,rk+qaq+1,a[i])-rk;
	m=read();block=max(1,(int)(n/sqrt(m*2.0/3)));
	for(rint i=1;i<=n;i++)pos[i]=(i-1)/block+1;
	for(rint i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	rint l=1,r=0;
	for(rint i=1;i<=m;i++){
		while(l<q[i].l)
			if((--cnt[a[l++]])==0)tans--;
		while(r>q[i].r)
			if((--cnt[a[r--]])==0)tans--;
		while(l>q[i].l)
			if((++cnt[a[--l]])==1)tans++;
		while(r<q[i].r)
			if((++cnt[a[++r]])==1)tans++;
		ans[q[i].id]=tans;
	}
	for(rint i=1;i<=m;i++)
        write(ans[i]),putchar('\n');
	return 0;
}