#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,a[2100000],l[2100000],r[2100000],tree[2100000],pos[2100000],nxt[2100000],lst[2100000],Ans[2100000];
set<pii> s; vector<int> vec[2100000],tmp[2100000];
char Getchar(){
    static char now[1<<20],*S,*T;
    if (T==S){
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
int read(){
    int x=0,f=1;
    char ch=Getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=Getchar();
    }
    while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
    return x*f;
}
void add(int x,int v){
    for (;x<=n;x+=x&-x) tree[x]=max(tree[x],v);
}
int query(int x){
    int res=0;
    for (;x;x-=x&-x) res=max(res,tree[x]);
    return res;
}
int getlst(int x){
    return (--s.lower_bound(pii(x+1,0)))->first;
}
int getnxt(int x){
    return (s.lower_bound(pii(x,0)))->first;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    m=read();
    for (int i=1;i<=m;i++){
        l[i]=read(); r[i]=read();
        vec[l[i]].push_back(i);
        tmp[r[i]].push_back(i);
    }
    for (int i=1;i<=2000000;i++) pos[i]=n+1;
    for (int i=n;i>=1;i--){
        nxt[i]=pos[a[i]]; add(nxt[i],nxt[i]-i-1);
        s.erase(pii(pos[a[i]],a[i]));
        pos[a[i]]=i;
        s.insert(pii(pos[a[i]],a[i]));
        for (int v:vec[i])
            Ans[v]=max(getlst(r[v])-l[v],query(r[v]));
//        i+1..nxt[i]-1
    }
    for (int i=1;i<=2000000;i++) pos[i]=0;
    for (int i=1;i<=n;i++){
        s.erase(pii(pos[a[i]],a[i]));
        pos[a[i]]=i;
        s.insert(pii(pos[a[i]],a[i]));
        for (int v:tmp[i])
            Ans[v]=max(Ans[v],r[v]-getnxt(l[v]));
    }
    for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}