#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4+10;
vector<int>v;
int n,m,f[N],pre[N];
int find(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin();
}
struct Seg_T{
    //对于1~N的每个位置的贝壳,建立每一颗线段树,
    //当前贝壳在之前出现过,把这个贝壳之前放置的位置 -1
    //当前位置i +1 ,代表一个不同的贝壳
    int root[N],idx = 0;
    struct node{
        int l,r,cnt;
    }tr[N*40];
    int build(int l,int r){
        int point = ++idx;
        if(l==r)return point;
        int mid = (l+r)>>1;
        tr[point].l = build(l,mid);
        tr[point].r = build(mid+1,r);
        return point;
    }
    void update(node &u){
        u.cnt = tr[u.l].cnt + tr[u.r].cnt ;
    }
    int insert(int a,int l,int r,int x,int c){
        int b = ++idx;
        tr[b] = tr[a];
        if(l==r){
            tr[b].cnt += c;
            return b;
        }
        int mid = (l+r)>>1;
        if(x<=mid)tr[b].l = insert(tr[a].l,l,mid,x,c);
        else tr[b].r = insert(tr[a].r,mid+1,r,x,c);
        update(tr[b]);
        return b;
    }
    int query(int u,int l,int r,int x){//条件:统计所有在 x 后的区间
        //查询 线段树 u内,下标在x之后的数目
        // u 就是root[r],这样完成了区间 l,r的统计
        if(l==r)return tr[u].cnt;
        int mid = (l+r)>>1;
        //x <=mid 时,整个右区间都满足条件
        if(x<=mid)return query(tr[u].l,l,mid,x)+tr[tr[u].r].cnt;
        else return query(tr[u].r,mid+1,r,x);
    }
}T;
int main(){
    memset(pre,-1,sizeof pre);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i]);
        v.push_back(f[i]);
    }
    sort(v.begin(),v.end());

    T.root[0] = T.build(1,n);

    for(int i=1;i<=n;i++){
        int x = find(f[i]);
        if(pre[x]==-1){
            //贝壳x没出现过,放在 i 的位置
            T.root[i] = T.insert(T.root[i-1],1,n,i,1);
        }
        else {
            //贝壳x在之前出现过,先把之前出现的贝壳x消除
            //然后把贝壳x放在 i 的位置,贪心的靠后放置
            int a = T.insert(T.root[i-1],1,n,pre[x],-1);
            //创建一个继承了之前的线段树并且修改了x的位置的新线段树
            T.root[i] = T.insert(a,1,n,i,1);
            //用这个线段树更新第 i 颗线段树
        }
        pre[x] = i;
    }

    scanf("%d",&m);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        //在第 r 颗线段树查询点 l 往后的不同贝壳种类数
        printf("%d\n",T.query(T.root[r],1,n,l));
    }
    return 0;
}