记录链接

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){register int t1=0,t2=0;register char x=getchar();while(x<'0' ||x>'9'){if(x=='-') t2|=1;x=getchar();}while(x>='0' && x<='9'){t1=(t1<<1)+(t1<<3)+(x^48),x=getchar();}return t2?-t1:t1;}
inline void write(int x){register int sta[105],top=0;if(x<0) putchar('-'),x=-x;do{sta[top++]=x%10,x/=10;}while(x);while(top) putchar(sta[--top]+48);}
int n,a[200005],b[200005],m,t,L[200005],R[200005],pos[200005],temp,last,temp_st[200005],ans[200005],now,st[200005],ed[200005],l=1,r,temp_l,temp_ed[200005];
struct que{
    int l,r,id;
}q[200005];
bool cmp(que x,que y){
    if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
    return x.r<y.r;
}
void build(){
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;
        R[i]=i*t;
    }
    if(R[t]<n){
        t++;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;i++) for(int j=L[i];j<=R[i];j++) pos[j]=i;
}
signed main(){
	n=read();
    for(int i=1;i<=n;i++){
        b[i]=read();
        a[i]=b[i];
    }
    m=read();
    for(int i=1;i<=m;i++){
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    build();
    sort(q+1,q+1+m,cmp);
    sort(b+1,b+1+n);
    temp=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+temp,a[i])-b;
    for(int i=1;i<=m;i++){
        if(pos[q[i].l]==pos[q[i].r]){
            for(int j=q[i].l;j<=q[i].r;j++) temp_st[a[j]]=0;
            for(int j=q[i].l;j<=q[i].r;j++){
                if(!temp_st[a[j]]) temp_st[a[j]]=j;
                ans[q[i].id]=max(ans[q[i].id],llabs(j-temp_st[a[j]]));
            }
            for(int j=q[i].l;j<=q[i].r;j++) temp_st[a[j]]=0;
        }
        else{
            if(pos[q[i].l]!=last){
                now=0;
                for(int j=l;j<=r;j++){
                    st[a[j]]=0;
                    ed[a[j]]=0;
                }
                l=R[pos[q[i].l]];
                r=l-1;
                last=pos[q[i].l];
            }
            while(r<q[i].r){
                r++;
                if(!st[a[r]]) st[a[r]]=r;
                ed[a[r]]=r;
                now=max(now,llabs(r-st[a[r]]));
            }
            temp_l=l;
            temp=now;
            while(temp_l>q[i].l){
                temp_l--;
                if(!temp_ed[a[temp_l]]) temp_ed[a[temp_l]]=temp_l;
                temp=max(temp,llabs(max(ed[a[temp_l]],temp_ed[a[temp_l]])-temp_l));
            }
            ans[q[i].id]=temp;
            while(temp_l<l){
                temp_ed[temp_l]=0;
                temp_l++;
            }
        }
    }
    for(int i=1;i<=m;i++){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}