玄关求调

#include<bits/stdc++.h>
using namespace std;
#define MAX 200010
#define int long long 
int n,a[MAX],b[MAX],siz,bnum,belong[MAX],m,tot;
int ans[MAX],cnt[MAX],st[MAX],clear[MAX],top;
int read(){
	int x=0; char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x;
}
struct node {
	int l,r,id;
}q[MAX];

bool cmp(node a,node b){
	return (belong[a.l]^belong[b.l] ? belong[a.l]<belong[b.l] :a.r<b.r);
}

int work(int l,int r){
	int last[MAX],res=0;
	for(int i=l;i<=r;i++) last[a[i]]=0;
	for(int i=l;i<=r;i++){
		if(!last[a[i]]) last[a[i]]=i;
		else res=max(res,i-last[a[i]]);
	}
	return res;
}

signed main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
	m=read();
	for(int i=1;i<=m;i++){
		q[i].l=read(); q[i].r=read();
		q[i].id=i;
	}
	siz=n/sqrt(m);
	bnum=ceil((double)n/siz);
	for(int i=1;i<=bnum;i++){
		for(int j=siz*(i-1)+1;j<=siz*i;j++){
			belong[j]=i;
		}
	}
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	sort(q+1,q+1+m,cmp);
	int l=0,r=0,lst=0,now=0;
	for(int i=1;i<=m;i++){
		if(belong[q[i].r]==belong[q[i].l]){
			ans[q[i].id]=work(q[i].l,q[i].r);
			continue;
		}
		if(belong[q[i-1].l]<belong[q[i].l]){
			for(int j=1;j<=top;j++) cnt[clear[j]]=st[clear[j]]=0;
			top=0;
			l=siz*belong[q[i].l];
			r=l-1;
			lst=now=0;
		}
		while(r<q[i].r){
			r++;
			cnt[a[r]]=r;
			if(!st[a[r]]) st[a[r]]=r,clear[++top]=a[r];
			now=max(now,r-st[a[r]]);
		}
		lst=now;
		while(l>q[i].l){
			l--;
			if(cnt[a[l]]) now=max(now,cnt[a[l]]-l);
			else cnt[a[l]]=l;
		}
		ans[q[i].id]=now;
		for(int j=siz*belong[q[i].l]-1;j>=l;j--){
			if(cnt[a[j]]==j) cnt[a[j]]=0;
		}
		now=lst;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}