rt，#4-#16 WA

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int maxn = 2e5+5;
int n,m,a[maxn],b[maxn],ans[maxn];
int block_size,bel[maxn],L[maxn],R[maxn];
int l,r,cur=1,mi[maxn],ma[maxn],ma1[maxn];
struct query{
    int l,r,id;
    bool operator<(const query &o)const{
        if(bel[l]==bel[o.l])return r<o.r;
        return l<o.l;
    }
}Q[maxn];
void bruteforce(const query &q){
    for(int i=q.l;i<=q.r;++i){
        if(!mi[a[i]])mi[a[i]]=i;
        ans[q.id]=max(ans[q.id],i-mi[a[i]]);
    }
    for(int i=q.l;i<=q.r;++i)mi[a[i]]=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    block_size=sqrt(n);
    for(int i=1;i<=n;++i){
        bel[i]=i/block_size+1;
        if(bel[i]!=bel[i-1]){
            L[bel[i]]=i;
            R[bel[i-1]]=i-1;
        }
    }
    R[bel[n]]=n;
    cin>>m;
    for(int i=1;i<=m;++i){
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+m+1);
    for(int i=1;i<=bel[n];++i){
        l=R[i]+1,r=R[i];
        while(bel[Q[cur].l]==i){
            if(bel[Q[cur].r]==i)bruteforce(Q[cur]);
            else{
                while(r<Q[cur].r){
                    ++r;
                    if(!mi[a[r]])mi[a[r]]=r;
                    ma[a[r]]=r;
                    ans[Q[cur].id]=max(ans[Q[cur].id],r-mi[a[r]]);
                }
                while(l>Q[cur].l){
                    --l;
                    if(!ma1[a[l]])ma1[a[l]]=l;
                    ans[Q[cur].id]=max(ans[Q[cur].id],max(ma[a[l]],ma1[a[l]])-l);
                }
                while(l<=R[i]){
                    ma1[a[l]]=0;
                    ++l;
                }
            }
            ++cur;
        }
        for(int j=l;j<=r;++j)mi[a[j]]=ma[a[j]]=0;
    }
    for(int i=1;i<=m;++i)cout<<ans[i]<<'\n';
    return 0;
}