无修改、询问区间种类数的问题可以很容易地用树状数组解决
我们先给询问按右端点排序，然后推着做，每次让a[i]++，表示i处新增了一个种类
但是这样会和前面的有重复，我们只要记下每个种类上次在哪里出现过，当这次又出现了，把前面的那次减掉就可以了
每次处理完之后，就可以计算所有右端点为i的区间的答案，就是这个区间右端点的前缀和减去左端点-1的前缀和
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=5e5+,maxm=1e6+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,tr[maxn];
int col[maxn],lst[maxm],ans[maxn];
struct Q{
int l,r,i;
}que[maxn]; inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){
for(;x<=N;x+=lowbit(x)) tr[x]+=y;
}
inline int query(int x){
int re=;for(;x;x-=lowbit(x)) re+=tr[x];return re;
} inline bool cmp(Q a,Q b){
return a.r<b.r;
} int main(){
int i,j,k;
N=rd();
for(i=;i<=N;i++) col[i]=rd();
M=rd();
for(i=;i<=M;i++){
que[i].l=rd(),que[i].r=rd(),que[i].i=i;
}sort(que+,que+M+,cmp);
for(i=,j=;i<=N;i++){
if(lst[col[i]]) add(lst[col[i]],-);
add(i,);lst[col[i]]=i;
for(;que[j].r==i;j++){
ans[que[j].i]=query(i)-query(que[j].l-);
}
}
for(i=;i<=M;i++) printf("%d\n",ans[i]);
return ;
}