#include<bits/stdc++.h>
using namespace std;
int rd()
{
    char c=getchar();int x=0;
    while(!(c>='0'&&c<='9'))
        c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+(c-'0');
        c=getchar();
    }
    return x;
}
const int N=2000005;
vector<pair<int,int>>ql[N],qr[N];
int n,q,a[N],mx[N<<2],tr[N<<2],tg,p[N],ans[N];
void upd(int k,int l,int r,int x,int v)
{
    if(l==r)
    {
        mx[k]=v;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) upd(k<<1,l,mid,x,v);
    else upd(k<<1|1,mid+1,r,x,v);
    mx[k]=max(mx[k<<1],mx[k<<1|1]);
}
int ask(int k,int l,int r,int a,int b)
{
    if(a>b)
        return 0;
    if(l==a&&r==b)
        return mx[k];
    int mid=l+r>>1;
    if(b<=mid) return ask(k<<1,l,mid,a,b);
    else if(a>mid) return ask(k<<1|1,mid+1,r,a,b);
    else return max(ask(k<<1,l,mid,a,mid),ask(k<<1|1,mid+1,r,mid+1,b));
}
void add(int k,int l,int r,int x,int v)
{
    if(l==r)
    {
        tr[k]+=v;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) add(k<<1,l,mid,x,v);
    else add(k<<1|1,mid+1,r,x,v);
    tr[k]=tr[k<<1]+tr[k<<1|1];
}
void ask1(int k,int l,int r,int a,int b)
{
    if(tg!=-1||!tr[k])
        return;
    if(l==r)
    {
        tg=l;
        return;
    }
    int mid=l+r>>1;
    if(a<=l&&r<=b)
    {
        ask1(k<<1,l,mid,a,b);
        ask1(k<<1|1,mid+1,r,a,b);
        return;
    }
    if(a<=mid) ask1(k<<1,l,mid,a,b);
    if(b>mid) ask1(k<<1|1,mid+1,r,a,b);
}
void ask2(int k,int l,int r,int a,int b)
{
    if(tg!=-1||!tr[k])
        return;
    if(l==r)
    {
        tg=l;
        return;
    }
    int mid=l+r>>1;
    if(a<=l&&r<=b)
    {
        ask2(k<<1|1,mid+1,r,a,b);
        ask2(k<<1,l,mid,a,b);
        return;
    }
    if(b>mid) ask2(k<<1|1,mid+1,r,a,b);
    if(a<=mid) ask2(k<<1,l,mid,a,b);
}
int main()
{
    n=rd();
    for(int i=1;i<=n;i++)
        a[i]=rd();
    q=rd();
    for(int i=1;i<=q;i++)
    {
        int l=rd(),r=rd();
        ql[r].emplace_back(l,i);
        qr[l].emplace_back(r,i);
    }    
    for(int i=1;i<=n;i++)
    {
        if(p[a[i]])
        {
            upd(1,1,n,p[a[i]],i-p[a[i]]-1);
            add(1,1,n,p[a[i]],-1);
        }
        p[a[i]]=i;
        add(1,1,n,i,1);
        for(auto j:ql[i])
        {
            int l=j.first,d=j.second;
            tg=-1;
            ask1(1,1,n,l,i);
            ans[d]=max(ans[d],i-tg);
            ans[d]=max(ans[d],ask(1,1,n,l,i));
        }
    }
    memset(tr,0,sizeof(tr));
    memset(p,0,sizeof(p));
    for(int i=n;i;i--)
    {
        if(p[a[i]])
            add(1,1,n,p[a[i]],-1);
        p[a[i]]=i;
        add(1,1,n,i,1);
        for(auto j:qr[i])
        {
            int r=j.first,d=j.second;
            tg=-1;
            ask2(1,1,n,i,r);
            ans[d]=max(ans[d],tg-i);
        }
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}