#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define N 2000005
#define inf 2147483647
#define LL long long
#define DB double
#define s_id set<int>::iterator
using namespace std;
int n,m,a[N],pos[N],nxt[N],lst[N],rk[N],l[N],r[N],rk2[N],ans[N],S[N<<2];set<int> T;
inline bool cmp(int x,int y){return lst[x]<lst[y];} inline bool cmp2(int x,int y){return l[x]<l[y];} inline bool cmp3(int x,int y){return nxt[x]>nxt[y];} inline bool cmp4(int x,int y){return r[x]>r[y];} 
inline void U(int x,int l,int r,int pos,int v){if(l==r){S[x]=v;return;}int mid=l+r>>1;if(mid>=pos) U(x<<1,l,mid,pos,v);else U(x<<1|1,mid+1,r,pos,v);S[x]=max(S[x<<1],S[x<<1|1]);}
inline int Q(int x,int l,int r,int ll,int rr){if(l>=ll&&r<=rr) return S[x];int mid=l+r>>1,res=0;if(mid>=ll) res=Q(x<<1,l,mid,ll,rr);if(mid<rr) res=max(res,Q(x<<1|1,mid+1,r,ll,rr));return res;}
struct FastIO{
    static const int S=1048576;
    char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
    inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
    FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
    template<typename T>FastIO& operator >> (T&ret){
        ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
    }
    FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
    template<typename T>FastIO& operator << (T x){
        if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
        while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
    }
    FastIO& operator << (char ch){pc(ch);return *this;}
    FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
//    freopen("data.in","r",stdin);
//    freopen("jxc.out","w",stdout);
    fin>>n;for(register int i=1;i<=n;i++) fin>>a[i],lst[i]=pos[a[i]],nxt[pos[a[i]]]=i,pos[a[i]]=i,rk[i]=i;sort(rk+1,rk+n+1,cmp);for(register int i=1;i<=n;i++) if(!nxt[i]) nxt[i]=n+1;
    fin>>m;for(register int i=1;i<=m;i++) fin>>l[i]>>r[i],rk2[i]=i;sort(rk2+1,rk2+m+1,cmp2);int now=1;for(register int i=1;i<=m;i++)
    {int x=rk2[i];while(now<=n&&lst[rk[now]]<l[x]) T.insert(rk[now]),now++;s_id it=T.upper_bound(r[x]);it--,ans[x]=*it-l[x];}
    now=n;for(register int i=m;i;i--){int x=rk2[i];while(now&&lst[rk[now]]>=l[x]) U(1,1,n,rk[now],rk[now]-lst[rk[now]]-1),now--;ans[x]=max(ans[x],Q(1,1,n,l[x],r[x]));}
    sort(rk+1,rk+n+1,cmp3),sort(rk2+1,rk2+m+1,cmp4),T.clear(),now=1;for(register int i=1;i<=m;i++)
    {int x=rk2[i];while(now<=n&&nxt[rk[now]]>r[x]) T.insert(rk[now]),now++;s_id it=T.lower_bound(l[x]);ans[x]=max(ans[x],r[x]-*it);}
    for(register int i=1;i<=m;i++) cout<<ans[i]<<'\n';return 0;
}