#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))

pii h[2000010];

int ans[2000010];
int num[2000010],n,m;

inline int rd()
{
    int x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

inline void print(int x)
{
    static char s[233];
    if (!x) { putchar('0');putchar('\n');return; }
    int tot=0;
    for (;x;x/=10) s[++tot]=x%10+'0';
    for (;tot;tot--) putchar(s[tot]);
    putchar('\n');
}

int lst[2000010],nxt[2000010];

int mn[8000010];

inline void build(int o,int l,int r)
{
    if (l==r) { mn[o]=nxt[l];return; }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    mn[o]=min(mn[o<<1],mn[o<<1|1]);
}

inline int query(int o,int l,int r,int x,int y)
{
    if (l>=x&&r<=y)
    {
        if (mn[o]>=x) return 0;
        if (l==r) return l;
        int mid=(l+r)>>1;
        if (mn[o<<1|1]<x) return query(o<<1|1,mid+1,r,x,y);
        return query(o<<1,l,mid,x,y);
    }
    int mid=(l+r)>>1,res=0;
    if (y>mid) res=query(o<<1|1,mid+1,r,x,y);
    if (x<=mid&&!res) res=query(o<<1,l,mid,x,y);
    return res;
}

inline void work()
{
    memset(lst,0,sizeof(lst));
    for (int i=1;i<=n;i++) nxt[i]=lst[num[i]],lst[num[i]]=i;
    build(1,1,n);
    for (int i=1;i<=m;i++) ans[i]=max(ans[i],query(1,1,n,h[i].first,h[i].second)-h[i].first);
}

vector<pii> v[2000010];
vector<int> g[2000010];

int c[2000010];

inline void add(int x,int y) { for (;x;x-=lowbit(x)) c[x]=max(c[x],y); }

inline int query(int x)
{
    int res=0;
    for (;x<=n;x+=lowbit(x)) res=max(res,c[x]);
    return res;
}

inline void pre_gao()
{
    for (int i=1;i<=n;i++)
    {
        if (lst[num[i]]) v[i].push_back(pii(lst[num[i]],i-lst[num[i]]-1));
        lst[num[i]]=i;
    }
    for (int i=1;i<=m;i++) g[h[i].second].push_back(i);
    for (int i=1;i<=n;i++)
    {
        for (pii hh:v[i]) add(hh.first,hh.second);
        for (int t:g[i]) ans[t]=max(ans[t],query(h[t].first));
    }
}

int main()
{
    n=rd();
    for (int i=1;i<=n;i++) num[i]=rd();
    m=rd();
    for (int i=1;i<=m;i++) h[i].first=rd(),h[i].second=rd(),ans[i]=0;
    pre_gao();
    work();
    reverse(num+1,num+n+1);
    for (int i=1;i<=m;i++) h[i].first=n-h[i].first+1,h[i].second=n-h[i].second+1,swap(h[i].first,h[i].second);
    work();
    for (int i=1;i<=m;i++) print(ans[i]);
    return 0;
}