tle on #8

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node
{
	int l,r,id;
}q[maxn];
int n,m,a[maxn],l[maxn],r[maxn],kid[maxn],tn,zz[maxn],stck[maxn],tot,bk[maxn],ans[maxn];
int cmp(node s1,node s2)
{
	return kid[s1.l]==kid[s2.l]?(s1.l%2==0?s1.r>s2.r:s1.r<s2.r):kid[s1.l]<kid[s2.l];
}
void add(int x)
{
	++bk[a[x]];
	if(bk[a[x]]==1)
	{
		stck[++tot]=a[x];
		zz[a[x]]=tot;
	}
	if(bk[a[x]]==2)
	{
		zz[stck[tot]]=zz[a[x]];
		swap(stck[tot],stck[zz[a[x]]]);
		
		zz[a[x]]=0;
		stck[tot]=0;
		--tot;
		
	}
}
void del(int x)
{
	--bk[a[x]];
//	cout<<a[x]<<' '<<bk[a[x]]<<' ';
	if(bk[a[x]]==1)
	{
		stck[++tot]=a[x];
		zz[a[x]]=tot;
	}
	if(bk[a[x]]==0)
	{
		zz[stck[tot]]=zz[a[x]];
		swap(stck[tot],stck[zz[a[x]]]);
//		zz[tot]=zz[a[x]];
		zz[a[x]]=0;
		stck[tot]=0;
		--tot;
//		cout<<stck[tot]<<endl;
	}
}
int read()
{
	char c=getchar();
	int d=0,f=0;
	while(!isdigit(c))
		f|=c=='-',c=getchar();
	while(isdigit(c))
		d=d*10+(c^48),c=getchar();
	return f?-d:d;
}
void print(int x)
{
	if(x>=10)
		print(x/10);
	putchar(x%10+'0');
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
//		cin>>a[i];
		a[i]=read();
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		q[i].l=read();
		q[i].r=read();
//		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	tn=sqrt(n);
	for(int i=1;i<=tn;i++)
		l[i]=r[i-1]+1,r[i]=i*tn;
	r[tn]=n;
	for(int i=1;i<=tn;i++)
		for(int j=l[i];j<=r[i];j++)
			kid[j]=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l)
			del(l++);
		while(l>q[i].l)
			add(--l);
		while(r<q[i].r)
			add(++r);
		while(r>q[i].r) 
			del(r--);
		ans[q[i].id]=stck[tot];
//		cout<<"####"<<q[i].l<<' '<<q[i].r<<' '<<stck[tot]<<endl;
	}
	for(int i=1;i<=m;i++)
	{
		print(ans[i]);
		puts("");
//		cout<<ans[i]<<endl;
	}
	return 0;
}