数据有毒

#include<bits/stdc++.h>
using namespace std;
int n,nm,m,a[500005],b[500005],d[500005],e[500005],f[500005],g[750],ll[750],rr[750],l=1,r=0,x,ans[500005];
struct node
{
	int id,l,r;
} c[500005];
bool operator<(node x,node y)
{
	return b[x.l]==b[y.l]?(b[x.l]&1?x.r<y.r:x.r>y.r):x.l<y.l;
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	cin>>m;
	for (int i=1;i<=m;++i)
	{
		c[i].id=i;
		scanf("%d%d",&c[i].l,&c[i].r);
	}
	nm=max(1,(int)round(n/sqrt(m)));
	for (int i=1;i<=n;++i)
	b[i]=(i-1)/nm+1;
	sort(c+1,c+m+1);
	for (int i=1;i<=500000;++i)
	{
		f[i]=(i-1)/707+1;
		if (ll[f[i]]==0)
		ll[f[i]]=i;
		rr[f[i]]=i;
	}
	for (int i=1;i<=m;++i)
	{
		while (l<c[i].l)
		{
			if (d[a[l]]==1)
			{
				--e[a[l]];
				--g[f[a[l]]];
			}
			--d[a[l]];
			if (d[a[l]]==1)
			{
				++e[a[l]];
				++g[f[a[l]]];
			}
			++l;
		}
		while (l>c[i].l)
		{
			--l;
			if (d[a[l]]==1)
			{
				--e[a[l]];
				--g[f[a[l]]];
			}
			++d[a[l]];
			if (d[a[l]]==1)
			{
				++e[a[l]];
				++g[f[a[l]]];
			}
		}
		while (r<c[i].r)
		{
			++r;
			if (d[a[r]]==1)
			{
				--e[a[r]];
				--g[f[a[r]]];
			}
			++d[a[r]];
			if (d[a[r]]==1)
			{
				++e[a[r]];
				++g[f[a[r]]];
			}
		}
		while (r>c[i].r)
		{
			if (d[a[r]]==1)
			{
				--e[a[r]];
				--g[f[a[r]]];
			}
			--d[a[r]];
			if (d[a[r]]==1)
			{
				++e[a[r]];
				++g[f[a[r]]];
			}
			--r;
		}
		for (x=1;x<=f[500000];++x)
		if (g[x])
		break;
		if (x<=f[500000])
		for (int j=ll[x];j<=rr[x];++j)
		if (e[j])
		{
			ans[c[i].id]=j;
			break;
		}
	}
	for (int i=1;i<=m;++i)
	cout<<ans[i]<<'\n';
}