rt，在块长=2135的情况下艹过了

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
namespace stO_cyx_Orz{
	#define ll long long
	static char buf[100000],*b=buf,*d=buf;
	#define gc b==d&&(d=(b=buf)+fread(buf,1,100000,stdin),b==d)?EOF:*b++	
	ll read(){ll ans=0,f=1;char c1=gc;while(c1<'0'||c1>'9'){if(c1=='-')f=-1;c1=gc;}while(c1>='0'&&c1<='9')ans=ans*10+c1-'0',c1=gc;return ans*f;}
	const int maxn = 1e6+5;
	int n,m,siz,block,belong[maxn];
	int cnt[maxn],a[maxn],l,r,ans,q[maxn];
	struct node{
		int l,r,x;
		int ans;
	}qwq[maxn];
	bool cmp(node a,node b){return (belong[a.l]^belong[b.l])?(belong[a.l]<belong[b.l]):((belong[a.l]&1)?a.r<b.r:a.r>b.r);}
	int mian(){
		n=read();
		for(int i=1;i<=n;++i)a[i]=read();m=read();
		for(int i=1;i<=m;i++)qwq[i].l=read(),qwq[i].r=read(),qwq[i].x=i;
		siz=2135;
		block=ceil(n*1.0/siz);
		for(int i=1;i<=n;i++)belong[i]=(i-1)/siz+1;
//		for(int i=1;i<=n;i++)cout<<belong[i]<<' ';
//		cout<<endl;
		sort(qwq+1,qwq+1+m,cmp);
		l=1;r=0;ans=0;
		for(int i=1;i<=m;i++){
			int ql=qwq[i].l,qr=qwq[i].r;
			while(l<ql)ans-=!--cnt[a[l++]];
			while(l>ql)ans+=!cnt[a[--l]]++;
			while(r<qr)ans+=!cnt[a[++r]]++;
			while(r>qr)ans-=!--cnt[a[r--]];
			q[qwq[i].x]=ans;
		}
		for(int i=1;i<=m;i++)printf("%d\n",q[i]);
		return 0;
	}
}
using namespace stO_cyx_Orz;
int main(){return mian();}