#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

struct node{

    int l,r,sum;

}T[maxn*];

int n,q,a[maxn],cnt,root[maxn],pos[];

void update(int &now,int pre,int val,int l,int r,int pos){

    T[++cnt]=T[pre],T[cnt].sum+=val,now=cnt;

    if(l==r) return;

    int mid=l+r>>;

    if(pos<=mid) update(T[now].l,T[pre].l,val,l,mid,pos);

    else update(T[now].r,T[pre].r,val,mid+,r,pos);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r) return T[rt].sum;

    int ans=,mid=l+r>>;

    if(L<=mid) ans+=query(L,R,l,mid,T[rt].l);

    if(R>mid) ans+=query(L,R,mid+,r,T[rt].r);

    return ans;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++){

        if(pos[a[i]]){

            update(root[i],root[i-],-,,n,pos[a[i]]);

            update(root[i],root[i],,,n,i);

        }else update(root[i],root[i-],,,n,i);

        pos[a[i]]=i;

    }

    scanf("%d",&q);

    while(q--){

        int l,r;

        scanf("%d%d",&l,&r);

        printf("%d\n",query(l,r,,n,root[r]));

    }

    return ;

}