能AC，但是能够更快吗，求大佬优化：

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
const int N=1e6+10;
struct problem{
	int l,r,id;
}q[N];
int a[N],k[N],ans[N],cnt[N],pre[N],suf[N],flag[N];
int n,m,l=1,r=0,now,t,sum; 
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57){
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
	return x*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
int cmp1(problem a,problem b){
	if(k[a.l]!=k[b.l]) return a.l<b.l;
	if(k[a.l]%2==0) return a.r>b.r;	
	return a.r<b.r;	
}
int cmp2(problem a,problem b){
	return a.id<b.id;
}
int main(){
	n=read();
	t=sqrt(n);
//	sum=ceil(double(n/t));
	for(int i=1;i<=n;i++) k[i]=(i-1)/t+1;
	for(int i=1;i<=n;i++) a[i]=read();
	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+m+1,cmp1);
	for(int i=1;i<=n;i++) pre[i]=flag[a[i]],flag[a[i]]=i;
	memset(flag,0x3f, sizeof(flag));
	for(int i=n;i>=1;i--) suf[i]=flag[a[i]],flag[a[i]]=i;
	for(int i=1;i<=m;i++){
		while(l>q[i].l) now+=(suf[--l]>r);
		while(l<q[i].l) now-=(suf[l++]>r);
		while(r>q[i].r) now-=(pre[r--]<l);
		while(r<q[i].r) now+=(pre[++r]<l);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;i++) 		 				write(ans[i]),putchar('\n');
//	sort(q+1,q+m+1,cmp2);
	return 0;
}