rt，用的莫队套值域分块

#include<bits/stdc++.h>
#define blk(i) (((i)-1)/B+1)
#define lft(i) (((i)-1)*B+1)
#define rgt(i) min((i)*B,n)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=600005;
int n,m,l=1,B,r,a[N],sa[N],sb[N],ans[N],cur[N],pre[N],nxt[N],lsh[N];
pii rec[N];
struct que
{
	int l,r,no;
	bool operator<(que a)
	{
		if(blk(l)^blk(a.l))return blk(l)<blk(a.l);
		if(blk(l)&1)return r<a.r;
		return r>a.r;
	}
}q[N];
void update(int u,int w)
{
	sa[u]+=w;
	sb[blk(u)]+=w;
}
void addl(int u)
{
	if(!rec[a[u]].fi)
	{
		rec[a[u]].fi=rec[a[u]].se=u;
		return;
	}
	update(rec[a[u]].se-rec[a[u]].fi,-1);
	rec[a[u]].fi=u;
	update(rec[a[u]].se-rec[a[u]].fi,1);
}
void addr(int u)
{
	if(!rec[a[u]].fi)
	{
		rec[a[u]].fi=rec[a[u]].se=u;
		return;
	}
	update(rec[a[u]].se-rec[a[u]].fi,-1);
	rec[a[u]].se=u;
	update(rec[a[u]].se-rec[a[u]].fi,1);
}
void dell(int u)
{
	if(rec[a[u]].fi==rec[a[u]].se)
	{
		rec[a[u]].fi=rec[a[u]].se=0;
		return;
	}
	update(rec[a[u]].se-rec[a[u]].fi,-1);
	rec[a[u]].fi=nxt[rec[a[u]].fi];
	update(rec[a[u]].se-rec[a[u]].fi,1);
}
void delr(int u)
{
	if(rec[a[u]].fi==rec[a[u]].se)
	{
		rec[a[u]].fi=rec[a[u]].se=0;
		return;
	}
	update(rec[a[u]].se-rec[a[u]].fi,-1);
	rec[a[u]].se=pre[rec[a[u]].se];
	update(rec[a[u]].se-rec[a[u]].fi,1);
}
int query()
{
	for(int i=blk(n);i;i--)if(sb[i])for(int j=rgt(i);j>=lft(i);j--)if(sa[j])return j;
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+n+1);
	int cnt=unique(lsh+1,lsh+n+1)-lsh;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
	for(int i=1;i<=n;i++)
	{
		pre[i]=cur[a[i]];
		cur[a[i]]=i;
	}
	for(int i=1;i<=n;i++)cur[i]=n+1;
	for(int i=n;i;i--)
	{
		nxt[i]=cur[a[i]];
		cur[a[i]]=i;
	}
	B=sqrt(n);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;
		q[i].no=i;
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++)
	{
		while(l>q[i].l)addl(--l);
		while(r<q[i].r)addr(++r);
		while(l<q[i].l)dell(l++);
		while(r>q[i].r)delr(r--);
		ans[q[i].no]=query();
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}