普通莫队+队列 wa on 2#求调

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int n,m,a[N],cnt[N],temp,bs,b[N],stk[N],top,idd[N];
struct dat{
	int l,r,id;
}q[N];
int ans[N];
bool cmp(dat x,dat y){
	if(b[x.l]!=b[y.l]) return x.l<y.l;
	if(b[x.l]&1) return x.r<y.r;
	return x.r>y.r;
}
inline void add(int t){
    ++cnt[t];
	if(cnt[t]==1){
		stk[++top]=t; 
		idd[t]=top; 
	}
	else if(cnt[t]==2){
		stk[idd[t]]=stk[top]; 
		idd[stk[top]]=idd[t]; 
		stk[top--]=idd[t]=0; 
	}
}
inline void del(int t){
    --cnt[t];
	if(cnt[t]==1){
		stk[++top]=t;
		idd[t]=top;
	}
	else if(!cnt[t]){
		stk[idd[t]]=stk[top];
		idd[stk[top]]=idd[t];
		stk[top--]=idd[t]=0;
	}
}
int main(){
	scanf("%d",&n);
	bs=sqrt(n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		b[i]=(i-1)/bs+1;
	}
	cin>>m;
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(r<q[i].r) add(a[++r]);
		while(r>q[i].r) del(a[r--]);
		while(l<q[i].l) add(a[l++]);
		while(l>q[i].l) del(a[--l]);
		ans[q[i].id]=stk[top];
	}
	for(int i=1;i<=m;i++) {
		printf("%d\n",ans[i]);
	}
	
	return 0;
}