#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+1;
            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-r+1,g[p]=k,void();
        int mid=l+r>>1;
        pushdown(p,mid,r);
        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,mid,r);
        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 lst[maxn],a[maxn],fa[maxn];
vector<pair<int,int>> Q[maxn];
int ans[maxn];
inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
    cin>>n;for(int i=1;i<=n;i++) cin>>a[i],fa[i]=i;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++){
        int x=lst[a[i]];A.modify(1,1,n,x+1,i,i);fa[getfa(x)]=getfa(x+1);
        lst[a[i]]=i;
        for(auto [x,id]:Q[i]) ans[id]=A.query(1,1,n,x,getfa(x));
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}