rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct node
{
    int l,r,x;
}a[maxn*40];
int read(){
    int s=0,f=0;
    char ch=getchar();
    while(!isdigit(ch)){
        f|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return f?-s:s;
}
int lst[maxn],rt[maxn<<1],n,cnt;
int newnode(int node)
{
    ++cnt;
    a[cnt]=a[node];
    return cnt;
}
int update(int l,int r,int rt,int x,int y)
{
    rt=newnode(rt);
    if(l==r)
    { 
        a[rt].x+=y;
        // cout<<l<<' '<<r<<' '<<y<<' '<<a[rt].x<<endl;
        return rt;
    }
    int mid=l+r>>1;
    if(x<=mid)
        a[rt].l=update(l,mid,a[rt].l,x,y);
    else
        a[rt].r=update(mid+1,r,a[rt].r,x,y);
    a[rt].x=a[a[rt].l].x+a[a[rt].r].x; 
    return rt;
}
int query(int l,int r,int rt,int x,int y)
{
    if(x<=l&&r<=y)
    {
        // cout<<l<<' '<<r<<' '<<a[rt].x<<endl;
        return a[rt].x;
    }
    int mid=l+r>>1,k=0;
    if(x<=mid)
        k+=query(l,mid,a[rt].l,x,y);
    if(mid<y)
        k+=query(mid+1,r,a[rt].r,x,y);
    return k;
}
 inline void write(int x)
 {
     char F[200];
     int tmp=x>0?x:-x ;
     if(x<0)putchar('-') ;
     int cnt=0 ;
        while(tmp>0)
        {
            F[cnt++]=tmp%10+'0';
            tmp/=10;
        }
        while(cnt>0)putchar(F[--cnt]) ;
 }
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        rt[i]=update(1,n,rt[i-1],i,1);
        if(lst[x]!=0)
        {
            // cout<<x<<endl;
            rt[i]=update(1,n,rt[i],lst[x],-1);
        }
        lst[x]=i;
    } 
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(); 
        write(query(1,n,rt[y],x,y));
        printf("\n");
    }
    return 0;
}