#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct stree
{
    int l,r,mn,mx;
}t[4200000];
struct query
{
    int l,r,id;
}b[2000005];
int a[2000005],ans[2000005],lst[2000005],A[2000005],n,q;
inline bool cmp(query x,query y)
{
    return x.r<y.r;
}
inline void build(int now,int l,int r)
{
    t[now].l=l,t[now].r=r;
    if(l==r)
    {
        t[now].mn=t[now].mx=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(now*2,l,mid),build(now*2+1,mid+1,r);
    t[now].mn=min(t[now*2].mn,t[now*2+1].mn);
    t[now].mx=max(t[now*2].mx,t[now*2+1].mx);
}
inline void change(int now,int p,int x)
{
    if(t[now].l==t[now].r)
    {
        t[now].mn=t[now].mx=x;
        return ;
    }
    if(t[now*2].r>=p) change(now*2,p,x);
    else change(now*2+1,p,x);
    t[now].mn=min(t[now*2].mn,t[now*2+1].mn);
    t[now].mx=max(t[now*2].mx,t[now*2+1].mx);
}
inline int qx(int now,int l,int r)
{
    if(t[now].l==l&&t[now].r==r) return t[now].mx;
    if(t[now*2].r>=r) return qx(now*2,l,r);
    if(t[now*2+1].l<=l) return qx(now*2+1,l,r);
    return max(qx(now*2,l,t[now*2].r),qx(now*2+1,t[now*2+1].l,r));
}
inline int qn(int now,int l,int r)
{
    if(t[now].l==l&&t[now].r==r) return t[now].mn;
    if(t[now*2].r>=r) return qn(now*2,l,r);
    if(t[now*2+1].l<=l) return qn(now*2+1,l,r);
    return min(qn(now*2,l,t[now*2].r),qn(now*2+1,t[now*2+1].l,r));
}
int main(int argc, char** argv) {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(int i=1;i<=q;i++) scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
    for(int i=1;i<=n;i++) a[i]=1e9;
    build(1,1,n);
    sort(b+1,b+q+1,cmp);
    int now=0;
    for(int i=1;i<=q;i++)
    {
        while(now<b[i].r)
        {
            ++now;
            if(lst[A[now]]) change(1,lst[A[now]],1e9);
            lst[A[now]]=now;
            change(1,now,now);
        }
        ans[b[i].id]=b[i].r-qn(1,b[i].l,b[i].r);
    }
    memset(lst,0,sizeof lst);
    for(int i=1;i<=n;i++) a[i]=1e9;
    build(1,1,n);
    for(int i=1;i<=q;i++) b[i].l=n-b[i].l+1,b[i].r=n-b[i].r+1,swap(b[i].l,b[i].r);
    sort(b+1,b+q+1,cmp);
    reverse(A+1,A+n+1);
    now=0;
    for(int i=1;i<=q;i++)
    {
        while(now<b[i].r)
        {
            ++now;
            if(lst[A[now]]) change(1,lst[A[now]],1e9);
            lst[A[now]]=now;
            change(1,now,now);
        }
        ans[b[i].id]=max(ans[b[i].id],b[i].r-qn(1,b[i].l,b[i].r));
    }
    memset(lst,0,sizeof lst);
    for(int i=1;i<=n;i++) a[i]=0;
    build(1,1,n);
    now=0;
    for(int i=1;i<=q;i++)
    {
        while(now<b[i].r)
        {
            ++now;
            if(lst[A[now]])
            {
                change(1,lst[A[now]]+1,now-lst[A[now]]-1);
        //        cout << now << " " << lst[A[now]] << "**\n";
            }
            lst[A[now]]=now;
        }
        ans[b[i].id]=max(ans[b[i].id],qx(1,b[i].l,b[i].r));
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}