#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=2e6+5;
int n,q;
#define ls p<<1
#define rs p<<1|1
struct seg1{
    int t[maxn<<2],g[maxn<<2];
    inline void pushup(int p){t[p]=min(t[ls],t[rs]);}
    inline void pushdown(int p,int l,int mid){
        if(g[p]){
            g[ls]=g[rs]=g[p];
            t[ls]=g[p]-l+1; 
            t[rs]=g[p]-mid;
            g[p]=0;
        }
    }
    void modify(int p,int l,int r,int ql,int qr,int k){
        if(ql<=l&&r<=qr) return t[p]=k-l+1,g[p]=k,void();
        int mid=l+r>>1;
        pushdown(p,l,mid);
        if(ql<=mid) modify(ls,l,mid,ql,qr,k);
        if(qr>mid) modify(rs,mid+1,r,ql,qr,k);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        // cout<<p<<' '<<l<<' '<<r<<' '<<g[p]<<' '<<t[p]<<'\n';
        if(ql<=l&&r<=qr) return t[p];
        int mid=l+r>>1,res=n+1;pushdown(p,l,mid);
        if(ql<=mid) res=query(ls,l,mid,ql,qr);
        if(qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
        return res;
    }
}A;
int nxt[maxn];
struct seg2{
    int t[maxn<<2];
    inline void pushup(int p){t[p]=max(t[ls],t[rs]);}
    void build(int p,int l,int r){
        if(l==r) return t[p]=nxt[l],void();
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr,int k){
        if(qr<l||ql>r||t[p]<=k) return 0; 
        if(l==r) return l;
        int mid=l+r>>1;
        if(ql<=l&&r<=qr)
            return (t[ls]>k?query(ls,l,mid,ql,qr,k):query(rs,mid+1,r,ql,qr,k));
        return query(ls,l,mid,ql,qr,k)?:query(rs,mid+1,r,ql,qr,k);
    }
}B;
int lst[maxn],a[maxn];
vector<pair<int,int>> Q[maxn];
int ans[maxn];
int main(){
    cin>>n;for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) nxt[i]=lst[a[i]]?:n+1,lst[a[i]]=i;
    B.build(1,1,n);cin>>q;
    for(int i=1,x,y;i<=q;i++) cin>>x>>y,Q[y].emplace_back(x,i);
    for(int i=1;i<=n;i++) lst[a[i]]=0;
    for(int i=1;i<=n;i++){
        A.modify(1,1,n,lst[a[i]]+1,i,i);
        lst[a[i]]=i;
        for(auto [x,id]:Q[i]){
            int w=B.query(1,1,n,x,i,i);
            // cout<<x<<' '<<i<<' '<<w<<'\n';
            ans[id]=A.query(1,1,n,x,w);
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';cout<<'\n';
}