莫队 + 奇偶优化死活卡在第 ⑨ 个点？
用的是栈储存答案的做法
求神仙康康

#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define MAXN 500005
#define reg register
#define inl inline
using namespace std;
int blk[MAXN];
struct Query
{
	int l,r,id;
	friend bool operator < (const Query &x,const Query &y)
	{
		return (blk[x.l]^blk[y.l])?x.l<y.l:((blk[x.l]&1)?x.r<y.r:x.r>y.r);
	}
}q[MAXN];
int n,m,a[MAXN],p[MAXN],ans[MAXN],stk[MAXN],pos[MAXN],top;
inl void Insert(reg int x)
{
	++p[x];
	if(p[x]==1)
	{
		stk[++top]=x;
		pos[x]=top;
	}
	else if(p[x]==2)
	{
		stk[pos[x]]=stk[top];
		pos[stk[top]]=pos[x];
		pos[x]=stk[top--]=0;
	}
}
inl void Erase(reg int x)
{
	--p[x];
	if(p[x]==1)
	{
		stk[++top]=x;
		pos[x]=top;
	}
	else if(!p[x])
	{
		stk[pos[x]]=stk[top];
		pos[stk[top]]=pos[x];
		pos[x]=stk[top--]=0;
	}
}
int main()
{
	scanf("%d",&n);
	reg int unt=sqrt(n);
	for(reg int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(reg int i=1;i<=m;++i)
	{
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	for(reg int i=1;i<=n;++i) blk[i]=i/unt;
	sort(q+1,q+m+1);
	reg int L=1,R=0;
	for(reg int i=1;i<=m;++i)
	{
		while(L<q[i].l) Erase(a[L++]);
		while(L>q[i].l) Insert(a[--L]);
		while(R<q[i].r) Insert(a[++R]);
		while(R>q[i].r) Erase(a[R--]);
		ans[q[i].id]=stk[top];
	}
	for(reg int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}