#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define X first
#define Y second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(i,a) for(int i=0;i<a.size();++i)
inline ll rd()
{
    char c=getchar();ll x=0,w=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*w;
}
const int P=998244353;
inline int pw(int a,int b)
{
    int r=1;for(;b;b>>=1,a=1ll*a*a%P)if(b&1)r=1ll*r*a%P;return r; 
}
const int nn=2000000,N=2000005;
int n,m,a[N],b[N],ans[N],mx[N*4];set<int>S;
vector<int>g[N],g2[N],g3[N];
#define ls x<<1,l,m
#define rs x<<1|1,m+1,r
void upd(int x,int l,int r,int tl,int tr,int v)
{
    if(tl<=l&&r<=tr)
    {
        mx[x]=max(mx[x],v);
        return;
    }
    int m=l+r>>1;
    if(tl<=m)upd(ls,tl,tr,v);
    if(tr>m)upd(rs,tl,tr,v);
}
int qmx(int x,int l,int r,int p)
{
    if(l==r)return mx[x];
    int m=l+r>>1;
    return max(mx[x],p<=m?qmx(ls,p):qmx(rs,p));
}
struct qr{int l,r,i;}q[N];
int main()
{
    n=rd();
    rep(i,1,n)a[i]=rd();
    m=rd();
    rep(i,1,m)
    {
        q[i].l=rd();
        q[i].r=rd();
        q[i].i=i;
        g[q[i].r].push_back(i);
        g3[q[i].l].push_back(i);
    }
    rep(i,1,nn)b[i]=0;
    rep(i,1,n)
    {
        if(b[a[i]]&&b[a[i]]!=i-1)g2[i-1].push_back(b[a[i]]+1);
        b[a[i]]=i;
    }
    rep(r,1,n)
    {
        for(int i=0;i<g[r].size();i++)
        {
            int x=g[r][i];
            ans[x]=qmx(1,1,n,q[x].l);
        }
        for(int i=0;i<g2[r].size();i++)
        {
            int l=g2[r][i];
            upd(1,1,n,1,l-1,r-l+1);
        }
    }
//    cout<<"WA"<<endl;
    rep(i,1,nn)b[i]=0;
    S.clear();S.insert(0);S.insert(n+1);
    rep(i,1,n)
    {
//        cout<<a[i]<<" "<<b[a[i]]<<endl;
        if(b[a[i]])S.erase(b[a[i]]);
        b[a[i]]=i;S.insert(i);
        for(int j=0;j<g[i].size();j++)
        {
            int x=g[i][j],l=q[x].l;
            int p=*S.lower_bound(l);
            ans[x]=max(ans[x],i-p);
        }
    }
//    cout<<"WA"<<endl;
    rep(i,1,nn)b[i]=0;
    S.clear();S.insert(0);S.insert(-n-1);
    per(i,n,1)
    {
//        cout<<a[i]<<" "<<b[a[i]]<<endl;
        if(b[a[i]])S.erase(-b[a[i]]);
        b[a[i]]=i;S.insert(-i);
        for(int j=0;j<g3[i].size();j++)
        {
            int x=g3[i][j],r=q[x].r;
            int p=*S.lower_bound(-r);
            p=-p;ans[x]=max(ans[x],p-i);
        }
    }
    rep(i,1,m)printf("%d\n",ans[i]);
    return 0;
}