#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define x first
#define y second
#define PII pair<int,int>
using namespace std;
const int mod = 1e9+7;
const int N = 1e6+10;
bool cmp(pair<int,PII>x,pair<int,PII>y){
    return x.y.y<y.y.y;
}
struct ST{
    struct node{
        int l,r,sum;
    }tree[N<<2];
    void update(node &u,node l,node r){
        u.sum = l.sum+r.sum;
    }
    void build(int u,int l,int r){
        if(l==r){
            tree[u]={l,r,0};
        }
        else {
            tree[u].l=l,tree[u].r=r;
            int mid = (l+r)>>1;
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
            update(tree[u],tree[u<<1],tree[u<<1|1]);
        }
    }
    void modify(int u,int pos,int c){
        if(tree[u].l==tree[u].r){
            tree[u].sum+=c;
            return ;
        }
        int mid = (tree[u].l+tree[u].r)>>1;
        if(pos<=mid)modify(u<<1,pos,c);
        else modify(u<<1|1,pos,c);
        update(tree[u],tree[u<<1],tree[u<<1|1]);
    }
    int query(int u,int l,int r){
        if(tree[u].l>=l and tree[u].r<=r)return tree[u].sum;
        int mid = (tree[u].l+tree[u].r)>>1;
        int res = 0;
        if(l<=mid)res=query(u<<1,l,r);
        if(r>mid)res+=query(u<<1|1,l,r);
        return res;
    }
}T;
pair<int,PII>q[N];
int pre[N],f[N],ans[N];
int n,m;
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&f[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r;scanf("%d%d",&l,&r);
        q[i].y={l,r};
        q[i].x=i;
    }
    sort(q+1,q+1+m,cmp);
    T.build(1,1,n);
    int k=1;
    //查询区间右端点从小到大排序,同时保证每个点第一次出现的位置尽量靠右
    //离线线段树
    for(int i=1;i<=m;i++){
        for(;k<=q[i].y.y;k++){
            if(pre[f[k]])T.modify(1,pre[f[k]],-1);
            T.modify(1,k,1);
            pre[f[k]]=k;
            //维护 1~k位置的每种贝壳出现的位置, 同种贝壳由多个的话尽量靠右
        }
        ans[q[i].x]=T.query(1,q[i].y.x,q[i].y.y);
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}
int main() {
    int TTT=1;//scanf("%d",&T);
    while(TTT--)solve();
}