#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<random>
#include<chrono>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 2000011,INF = 1e9+233;
int n;
struct Segment_Tree
{
    int t[MAXN<<2|1];
#define rt t[num]
    void init(){memset(t,-0x3f,sizeof t);}
    void modify(un ql,un qr,int k,un l=1,un r=n,un num=1)
    {
        if(ql>qr)return;
        if(ql<=l&&r<=qr){umax(rt,k);return;}
        un mid=(l+r)>>1;
        if(ql<=mid)modify(ql,qr,k,l,mid,num<<1);
        if(qr>mid)modify(ql,qr,k,mid+1,r,num<<1|1);
    }
    int Query(un pos,un l=1,un r=n,un num=1)
    {
        if(l==r)return rt;
        un mid=(l+r)>>1;
        if(pos<=mid)return max(Query(pos,l,mid,num<<1),rt);
        else return max(Query(pos,mid+1,r,num<<1|1),rt);
    }
}sgt[3];
struct one{int y1,y2,type,k;};
//1:L  2:R  3 middle
std::vector<pii>Q1[MAXN],Q2[MAXN];
int a[MAXN],res[MAXN],lst[MAXN];
int main()
{
    sgt[0].init(),sgt[1].init(),sgt[2].init();
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    int m=read();
    for(int i=1;i<=m;++i){int l=read(),r=read();Q1[r].push_back(pii(l,i)),Q2[l].push_back(pii(r,i));}
    for(int i=1;i<=n;++i)
    {
        int x=a[i];
        sgt[0].modify(lst[x]+1,i,i);//L
        sgt[2].modify(1,lst[x],i-lst[x]-1);
        lst[x]=i;
        for(auto p:Q1[i])
        {
            int l=p.first;
            res[p.second]=max(-l+sgt[0].Query(l),sgt[2].Query(l));
        }
    }
    for(int i=1;i<MAXN;++i)lst[i]=n+1;
    for(int i=n;i;--i)
    {
        int x=a[i];
        sgt[1].modify(i,lst[x]-1,-i);
        lst[x]=i;
        for(auto p:Q2[i])
        {
            int r=p.first;
            umax(res[p.second],r+sgt[1].Query(r));
        }
    }
    for(int i=1;i<=m;++i)printf("%d\n",res[i]);
    return 0;
}