https://www.luogu.com.cn/record/221877772

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int val[maxn],book[maxn],n,m,len,tot;
int pos[maxn],fin[maxn],ans[maxn];
int posl[maxn],posr[maxn],sta[maxn],stal[maxn],star[maxn];
struct node{
	int l,r,id;
}qry[maxn];
inline bool cmp(node u,node v){
	return pos[u.l]!=pos[v.l]?u.l<v.l:u.r<v.r;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>val[i],book[i]=val[i];
	sort(book+1,book+1+n);
	tot=unique(book+1,book+1+n)-book-1;
	for(int i=1;i<=n;i++){
		val[i]=lower_bound(book+1,book+1+tot,val[i])-book;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>qry[i].l>>qry[i].r;
		qry[i].id=i;
	}
	len=max(1,n/(int)sqrt(m));
	for(int i=1;i<=n;i++) pos[i]=(i+len-1)/len;
	for(int i=1;i<=pos[n];i++) fin[i]=min(n,i*len);
	for(int i=1;i<=tot;i++) posl[i]=n+1,posr[i]=0;
	sort(qry+1,qry+1+m,cmp);
	int pl,pr,top=0,tmp=0,res=0,last=0;
	for(int i=1;i<=m;i++){
		if(pos[qry[i].l]==pos[qry[i].r]){
			while(top){
				posl[sta[top]]=stal[top];
				posr[sta[top]]=star[top];
				top--;
			}
			pl=fin[pos[qry[i].l]]+1,pr=fin[pos[qry[i].l]];
			res=last=0;
			for(int i=qry[i].l;i<=qry[i].r;i++){
				sta[++top]=val[i];
				stal[top]=posl[val[i]];
				star[top]=posr[val[i]];
				posl[val[i]]=min(posl[val[i]],i);
				posr[val[i]]=max(posr[val[i]],i);
				res=max(res,posr[val[i]]-posl[val[i]]);
			}
			ans[qry[i].id]=res;
			res=last;
			while(top){
				posl[sta[top]]=stal[top];
				posr[sta[top]]=star[top];
				top--;
			}
		}
		else if(pos[qry[i].l]!=pos[qry[i-1].l]){
			while(top){
				posl[sta[top]]=stal[top];
				posr[sta[top]]=star[top];
				top--;
			}
			pl=fin[pos[qry[i].l]]+1,pr=fin[pos[qry[i].l]];
			res=last=0;
			while(pr<qry[i].r){
				++pr;
				sta[++top]=val[pr];
				stal[top]=posl[val[pr]];
				star[top]=posr[val[pr]];
				posl[val[pr]]=min(posl[val[pr]],pr);
				posr[val[pr]]=max(posr[val[pr]],pr);
				res=max(res,posr[val[pr]]-posl[val[pr]]);
			}
			last=res,tmp=top;
			while(pl>qry[i].l){
				--pl;
				sta[++top]=val[pl];
				stal[top]=posl[val[pl]];
				star[top]=posr[val[pl]];
				posl[val[pl]]=min(posl[val[pl]],pl);
				posr[val[pl]]=max(posr[val[pl]],pl);
				res=max(res,posr[val[pl]]-posl[val[pl]]);
			}
			ans[qry[i].id]=res;
			res=last,pl=fin[pos[qry[i].l]]+1;
			while(top>tmp){
				posl[sta[top]]=stal[top];
				posr[sta[top]]=star[top];
				top--;
			}
		}
		else{
			while(pr<qry[i].r){
				++pr;
				sta[++top]=val[pr];
				stal[top]=posl[val[pr]];
				star[top]=posr[val[pr]];
				posl[val[pr]]=min(posl[val[pr]],pr);
				posr[val[pr]]=max(posr[val[pr]],pr);
				res=max(res,posr[val[pr]]-posl[val[pr]]);
			}
			last=res,tmp=top;
			while(pl>qry[i].l){
				--pl;
				sta[++top]=val[pl];
				stal[top]=posl[val[pl]];
				star[top]=posr[val[pl]];
				posl[val[pl]]=min(posl[val[pl]],pl);
				posr[val[pl]]=max(posr[val[pl]],pl);
				res=max(res,posr[val[pl]]-posl[val[pl]]);
			}
			ans[qry[i].id]=res;
			res=last,pl=fin[pos[qry[i].l]]+1;
			while(top>tmp){
				posl[sta[top]]=stal[top];
				posr[sta[top]]=star[top];
				top--;
			}
		}
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}