#include <cstdio>

#include <algorithm>

using namespace std;

const int N=1000010;

int n,m,c[N],a[N],pre[N],nxt[N],ans[N];

struct data{int l,r,id;}p[N];

bool cmp(data a,data b){return a.l<b.l;}

void add(int x,int val){while(x<=n+1)c[x]+=val,x+=x&-x;}

int query(int x){int s=0;while(x)s+=c[x],x-=x&-x;return s;}

int main(){

    while(~scanf("%d",&n)){

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

        for(int i=1;i<N;i++)pre[i]=n+1;

        for(int i=n;i;i--){

            nxt[i]=pre[a[i]];

            pre[a[i]]=i;

        }

        for(int i=1;i<N;i++)add(pre[i],1);

        scanf("%d",&m);

        for(int i=1;i<=m;i++)scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;

        sort(p+1,p+m+1,cmp);

        int t=1;

        for(int i=1;i<=m;i++){

            while(t<p[i].l){

                add(t,-1);

                add(nxt[t],1);

                t++;

            }ans[p[i].id]=query(p[i].r);

        }

        for(int i=1;i<=m;i++)printf("%d\n",ans[i]);

    }return 0;

}