#include <bits/stdc++.h>
using namespace std;
const int N=1000000+5;
struct sdf{
    int l,r,pt;
}b[N];
int a[N],c[N],num[N]={0};
int ans[N]={0};
int n,m;
bool cmp(sdf x,sdf y){
    if (x.r!=y.r)return x.r<y.r;
    return x.l<y.l;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y){
    for (int i=x;i<=n;i+=lowbit(i)){
        c[i]+=y;
    }
    return ;
}
int getsum(int x){
    int t=0;
    for (int i=x;i>0;i-=lowbit(i)){
        t+=c[i];
    }
    return t;
}
int main(){
    freopen ("diff.in","r",stdin);
    freopen ("diff.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    cin>>m;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&b[i].l,&b[i].r);
        b[i].pt=i;
    }
    sort(b+1,b+m+1,cmp);
    int j=1;
    for (int i=1;i<=n;i++){
        if (num[a[i]]!=0){
            add(num[a[i]],-1);
        }
        add(i,1);num[a[i]]=i;
        while(j<=m&&b[j].r<i)j++;
        //cout<<i<<' '<<b[j].r<<" "<<b[j].pt<<endl;
        while(j<=m&&b[j].r==i){
            ans[b[j].pt]=getsum(b[j].r)-getsum(b[j].l-1);
            j++;
        }
    }
    for (int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}