莫队92pts TLE on#9 #10，卡常实在卡不动了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+25;
int n,a[N],m;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0;
    char ch=nc();
    while(ch<48||ch>57)
        ch=nc();
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
	return x;
}
void write(int x){
    if(x<0) putchar_unlocked('-'),x=-x;
    if(x>9) write(x/10);
    putchar_unlocked(x%10+'0');
    return;
}
struct Query{
    int l,r,id;
}q[N];
int pos[N],mp[N],ans[N],from[N];
bool cmp(Query a,Query b){
	if(pos[a.l]!=pos[b.l]) return a.l<b.l;
	if(pos[a.l]%2==0) return a.r>b.r;
	return a.r<b.r;
}
int tot=0;
inline void add(int x){if(!mp[a[x]])++tot;mp[a[x]]++;}
inline void del(int x){mp[a[x]]--;if(!mp[a[x]])--tot;}
int ls;
int main(){
    int n;
    cin>>n;
    int blockl=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!from[a[i]])
        from[a[i]]=++ls;
        a[i]=from[a[i]];
        pos[i]=i/blockl;
    }
    m=read();
    for(int i=1;i<=m;i++){
        q[i].l=read(),q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>q[i].l)l--,add(l);
        while(r<q[i].r)r++,add(r);
        while(l<q[i].l)del(l),l++;
        while(r>q[i].r)del(r),r--;
        ans[q[i].id]=tot;
    }
    for(int i=1;i<=m;i++)
       write(ans[i]),puts("");
}