#include<bits/stdc++.h>
using namespace std;
int n,m; 
const int maxn=1e8+10;
int a[maxn];
int v[maxn];
int c[maxn];
int ans[maxn];
struct node{
    int l,r,id;
}q[maxn];//存储询问 
void read(int &x){//快读模板 
    char ch=getchar();int f=1;x=0;
    while(!isdigit(ch) && ch^'-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}
int lowbit(int x)//树状数组核心*1 
{
    return x&-x;
}
bool cmp(const node a,const node b){//排序是万能的 
    return a.r<b.r;
}
void update(int val,int t){//树状数组核心*2
    for(int i=val;i<n+10;i+=lowbit(i)){
        c[i]+=t;
    }
}
int query(int val){//树状数组核心*3
    int t=0;
    for(int i=val;i>0;i-=lowbit(i)){
        t+=c[i];
    }
    return t;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++){//输入 
        read(a[i]);
    }
    read(m);
    for(int i=1;i<=m;i++){//输入 
        read(q[i].l);
        read(q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);//排序 
    int next=1;
    for(int i=1;i<=m;i++){
        for(int j=next;j<=q[i].r;j++){
            if(v[a[j]]){
                update(v[a[j]],-1);
            }
            update(j,1);
            v[a[j]]=j;
        }
        next=q[i].r+1;
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);//存入答案 
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}