92莫队，求卡常

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,ans,block,l=1,r,tot,a[1000005],su[1000005],lsh[1000005];
struct node{int first,second,it;}qu[1000005];
pair<int,int>out[1000005];
inline void read(int& a) {
	int s=0,w=1;char ch = getchar();
	while(ch<'0'||ch>'9'){
		if (ch=='-')w=-1;ch=getchar();
	}while(ch>='0'&&ch<='9') {
		s=s*10+ch-'0';ch=getchar();
	}a=s*w;
}
bool cmp(node x,node y){
	if(x.first/block==y.first/block){
		if(x.first/block%2==0)return x.second<y.second;
		else return x.second>y.second;
	}
	return x.first/block<y.first/block;
}signed main(){
	//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;block=sqrt(n);for(int i=1;i<=n;i++){
		read(a[i]);if(lsh[a[i]])a[i]=lsh[a[i]];
		else a[i]=lsh[a[i]]=++tot;
	}
	cin>>q;for(int i=1;i<=q;i++){read(qu[i].first);read(qu[i].second);qu[i].it=i;}
	sort(qu+1,qu+q+1,cmp);for(int i=1;i<=q;i++){
		int dl=qu[i].first,dr=qu[i].second;
		while(r<dr){r++;su[a[r]]++;if(su[a[r]]==1)ans++;}
		while(l>dl){l--;su[a[l]]++;if(su[a[l]]==1)ans++;}
		while(r>dr){su[a[r]]--;if(su[a[r]]==0)ans--;r--;}
		while(l<dl){su[a[l]]--;if(su[a[l]]==0)ans--;l++;}
		out[i].first=qu[i].it,out[i].second=ans;
	}sort(out+1,out+1+q);for(int i=1;i<=q;i++)cout<<out[i].second<<'\n';
	return 0;
}