#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))f^=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;y>>=1;
    }
    return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int n,m,p[2000010],ql[2000010],qr[2000010],ans[2000010];
std::vector<int>Q[2000010];std::set<int>S;
int col_end[2000010],next[2000010],len[2000010];
int max[5000010];
#define mid ((l+r)>>1)
void build(int x,int l,int r){
    if(l==r){max[x]=len[l];return;}
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    max[x]=std::max(max[x<<1],max[x<<1|1]);
}
void update(int x,int l,int r,int p){
    if(l==r){max[x]=0;return;}
    if(p<=mid)update(x<<1,l,mid,p);
    else update(x<<1|1,mid+1,r,p);
    max[x]=std::max(max[x<<1],max[x<<1|1]);
}
int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R)return max[x];
    if(L<=mid)
        if(mid<R)return std::max(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
        else return query(x<<1,l,mid,L,R);
    else return query(x<<1|1,mid+1,r,L,R);
}
void solve(){
    memset(col_end,-1,sizeof col_end);
    for(int i=1;i<=n;++i)Q[i].clear();
    for(int i=1;i<=m;++i)Q[ql[i]].push_back(i);
    for(int i=1;i<=n;++i){
        next[i]=0;
        if(col_end[p[i]]==-1){
            S.insert(i);
            len[i]=0;
        }else{
            next[col_end[p[i]]]=i;
            len[i]=i-col_end[p[i]]-1;
        }
        col_end[p[i]]=i;
    }
    build(1,1,n);
    for(int l=1;l<=n;++l){
        for(int i:Q[l]){
            ans[i]=std::max({ans[i],*--S.upper_bound(qr[i])-l,query(1,1,n,l,qr[i])});
        }
        S.erase(l);
        if(next[l]){
            S.insert(next[l]);
            update(1,1,n,next[l]);
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
#endif
    n=gi();
    for(int i=1;i<=n;++i)p[i]=gi();
    m=gi();
    for(int i=1;i<=m;++i)ql[i]=gi(),qr[i]=gi();
    solve();
    std::reverse(p+1,p+n+1);
    for(int i=1;i<=m;++i)std::swap(ql[i],qr[i]),ql[i]=n-ql[i]+1,qr[i]=n-qr[i]+1;
    solve();
    for(int i=1;i<=m;++i)printf("%d\n",ql[i]<=qr[i]?ans[i]:0);
    return 0;
}