/*在线求区间内不同的数的个数：从头到尾添加到线段树（不是权值线段树，是存值的线段树）中

如果此数之前出现过就先减去，接着再加，最后在区间(l,r)中找到root[r]这个历史版本*/

#include<map>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define dir(a,b) (a>>b)

const int Max=;

int root[Max],tot,val[Max];

struct node

{

    int lef,rig,sum;

}msegtr[Max*];

map<int,int> mp;

void Init()

{

    tot=;

    msegtr[].lef=msegtr[].rig=msegtr[].sum=;

    root[]=;

    mp.clear();

    return;

}

void Create(int sta,int enn,int &x,int y,int pos,int aad)

{

    msegtr[++tot]=msegtr[y];

    msegtr[tot].sum+=aad;

    x=tot;

    if(sta==enn)

        return;

    int mid=dir(sta+enn,);

    if(mid>=pos)

        Create(sta,mid,msegtr[x].lef,msegtr[y].lef,pos,aad);

    else

    Create(mid+,enn,msegtr[x].rig,msegtr[y].rig,pos,aad);

    return;

}

int Query(int sta,int enn,int x,int y)//只有左边有界限

{

    if(sta>=y)

        return msegtr[x].sum;

    int mid=dir(sta+enn,);

    if(mid>=y)

        return Query(sta,mid,msegtr[x].lef,y)+msegtr[msegtr[x].rig].sum;

    else

        return Query(mid+,enn,msegtr[x].rig,y);

}

int main()

{

    int n,m,temp;

    int lef,rig;

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

    {

         Init();

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

    {

        scanf("%d",&val[i]);

        if(!mp.count(val[i]))//直接加

        {

            Create(,n,root[i],root[i-],i,);//注意是在i这个位置加1，不是权值线段树的val[i]位置加1

        }

        else

        {

            Create(,n,temp,root[i-],mp[val[i]],-);//先在原位置减去1

            Create(,n,root[i],temp,i,);

        }

        mp[val[i]]=i;

    }

    scanf("%d",&m);

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

    {

        scanf("%d %d",&lef,&rig);

        printf("%d\n",Query(,n,root[rig],lef));//在rig的历史版本上找(lef,rig)的值

    }

    }

    return ;

}