MX刚学莫队，10pts求条

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return x*f;
}
int n,nn,m,a[200005],b[200005],ans[200005];
int bl,bl_cnt,pos[200005];
int now,tmp,res,cnt2,ll[200005],rr[200005],clear[200005],lst[200005];
struct query{int l,r,id;}q[200005];
struct block{int l,r;}k[200005];
bool cmp(query x,query y){return pos[x.l]^pos[y.l]?pos[x.l]<pos[y.l]:x.r<y.r;}
int main(){
//	freopen("P5906_2.in","r",stdin);
//	freopen("P5906_2.txt","w",stdout);
	n=read(),bl=sqrt(n),bl_cnt=n/bl;
	for(int i=1;i<=n;i++)a[i]=b[i]=read(),pos[i]=(i-1)/bl+1;
	sort(b+1,b+n+1),nn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+nn+1,a[i])-b;
	m=read();
	for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=bl_cnt;i++)k[i].l=k[i-1].r+1,k[i].r=k[i].l+bl-1;
	if(k[bl_cnt].r<n)++bl_cnt,k[bl_cnt].l=k[bl_cnt-1].r+1,k[bl_cnt].r=n;
	for(int i=1,j=1;i<=bl_cnt;i++){
		int l=0,r=k[i].r;
		now=tmp=res=cnt2=0;
		while(pos[q[j].l]==i){
			l=k[i].r+1;
			if(q[j].r-q[j].l<=bl){
				for(int o=q[j].l;o<=q[j].r;o++)lst[a[o]]=0;
				for(int o=q[j].l;o<=q[j].r;o++)lst[a[o]]?res=max(res,o-lst[a[o]]):lst[a[o]]=o;
				ans[q[j].id]=res;
			}else{
				while(r<q[j].r){
					++r;
					rr[a[r]]=r;
					if(!ll[a[r]])ll[a[r]]=r,clear[++cnt2]=a[r];
					now=max(now,rr[a[r]]-ll[a[r]]);
				}
				tmp=now;
				while(l>q[j].l){
					--l;
					if(!rr[a[l]])rr[a[l]]=l;
					now=max(now,rr[a[l]]-l);
				}
				ans[q[j].id]=now;
				now=tmp;
				while(l<=k[i].r)rr[a[l]]==l?rr[a[l]]=0:0,++l;
			}
			++j;
		}
		for(int o=1;o<=cnt2;o++)ll[clear[o]]=rr[clear[o]]=0;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}