萌新刚学回滚莫队，4pts剩下全T求调

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
struct qry
{
	int l,r,id,ans;
	friend bool operator < (qry a,qry b)
	{
		return a.id<b.id;
	}
}q[200005];
int n,m,sl,a[200005],lnk[200005],an,sid[200005],el[200005],er[200005],bpl[20005],bpr[20005],bpd,maxd,l,r;
inline void read(int &x)
{
	char c=getchar();x=0;
	while(!isdigit(c)) x=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
}
inline bool sty(qry a,qry b)
{
	if(sid[a.l]^sid[b.l]) return a.l<b.l;
	return a.r<b.r;
}
inline int tai(int s){return s*sl;}
inline int hea(int s){return tai(s-1)+1;}
inline void add(int x,int p,bool d) //d=0:from left | d=1:from right
{
	if(el[x]==p) return;
	if(el[x]==inf&&er[x]==0) el[x]=er[x]=p;
	else
		if(d) er[x]=p;
		else if(!d) el[x]=p;
	maxd=max(maxd,er[x]-el[x]);
}
inline void force()
{
	for(int i=l;i<=r;i++)
	{
		if(el[a[i]]>=inf) el[a[i]]=i;
		else maxd=max(maxd,i-el[a[i]]),er[a[i]]=i;
	}
}
inline void backup()
{
	for(int i=tai(sid[l]);i<=r;i++)
	{
		if(bpl[a[i]]>=inf) bpl[a[i]]=i;
		else bpd=max(bpd,i-bpl[a[i]]),bpr[a[i]]=i;
	}
}
inline void reload()
{
	for(int i=l;i<=tai(sid[l])-1;i++) el[a[i]]=bpl[a[i]],er[a[i]]=bpr[a[i]];
	maxd=bpd;
	l=tai(sid[l]);
}
inline void clear()
{
	maxd=bpd=0;
	for(int i=hea(sid[l]);i<=r;i++) el[a[i]]=bpl[a[i]]=inf,er[a[i]]=bpr[a[i]]=0;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	read(m);
	sl=n/sqrt((m<<1)/3);
	for(int i=1;i<=m;i++) read(q[i].l),read(q[i].r),q[i].id=i,lnk[i]=a[i];
	sort(lnk+1,lnk+n+1);an=unique(lnk+1,lnk+n+1)-lnk-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(lnk+1,lnk+an+1,a[i])-lnk,sid[i]=(i-1)/sl+1;
	sort(q+1,q+m+1,sty);
	for(int i=1;i<=an;i++) el[i]=bpl[i]=inf;
	l=inf;r=0;
	for(int i=1;i<=m;i++)
	{
		if(sid[q[i].l]==sid[q[i].r])
		{
			l=q[i].l;r=q[i].r;
			clear();
			force();
			q[i].ans=maxd;
			r=0;
		}
		else if(sid[q[i].l]^sid[l]||!r)
		{
			if(!r) r=q[i].r;clear();
			l=q[i].l;r=q[i].r;force();backup();
			q[i].ans=maxd;
		}
		else
		{
			reload();
			while(r<q[i].r) r++,add(a[r],r,1);
			while(l>q[i].l) l--,add(a[l],l,0);
			q[i].ans=maxd;
		}
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++) printf("%d\n",q[i].ans);
	return 0;
}