#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
int n;
int a[N],ans[N];
int q;
int block,l,r;
int L[N],R[N];
int ed[N],st[N];
int rub[N],tt;
int sta[N];
struct Query{
    int l,r,id;
}Q[N];
bool cmp(Query a,Query b){
    if((a.l-1)/block+1==(b.l-1)/block+1) return a.r<b.r;
    return (a.l-1)/block+1<(b.l-1)/block+1;
}
void work(int id){
    for(int i=Q[id].l;i<=Q[id].r;i++){
        if(!sta[a[i]]) sta[a[i]]=i;
        ans[Q[id].id]=max(ans[Q[id].id],i-sta[a[i]]);
    }
    for(int i=Q[id].l;i<=Q[id].r;i++) sta[a[i]]=0;
}
vector<int> alls;
int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]<x) l=mid+1;
        else r=mid;
    }
    return r+1;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),alls.push_back(a[i]);
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    for(int i=1;i<=n;i++) a[i]=find(a[i]);
    block=max(1,(int)sqrt(n));
    scanf("%d",&q);
    for(int i=1;i<=q;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
    sort(Q+1,Q+1+q,cmp);
    for(int i=1,j=1;j<=(n-1)/block+1;j++){
        l=min(n,j*block)+1,r=l-1;
        tt=0;
        int res=0;
        for(;(Q[i].l-1)/block+1==j;i++){
            if((Q[i].r-1)/block+1==(Q[i].l-1)/block+1){
                work(i);
                continue;
            }
            while(r<Q[i].r){
                r++;
                ed[a[r]]=r;
                if(!st[a[r]]) st[a[r]]=r,rub[++tt]=a[r];
                res=max(res,r-st[a[r]]);
            }
            int tmp=res;
            while(l>Q[i].l){
                l--;
                if(ed[a[l]]) tmp=max(tmp,ed[a[l]]-l);
                else ed[a[l]]=l;
            }
            ans[Q[i].id]=tmp;
            while(l<min(n,j*block)+1){
                if(ed[a[l]]==l) ed[a[l]]=0;
                l++;
            }
        }
        while(tt){
            st[rub[tt]]=ed[rub[tt]]=0;
            tt--;
        }
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}