翻了一圈讨论区把能找到的优化差不多都加上去了，结果一直卡在 TLE #8 过不去。值域分块还不会，所以使用的是普通莫队。

谢谢各位啦！

#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int a[N],be[N];
int buc[N]; 
int ansi[N];
int T;
int sum;
int pos[N];
int stk[N],top;

struct node{
	 int l,r,id;
}q[N];

bool cmp(node x,node y){
	if(be[x.id]==be[y.id]){
		if(be[x.id]&1==0) return x.r<y.r;
		return x.r>y.r;
	}
	return x.l<y.l;
}

inline void add(int x){
	buc[a[x]]++;
	if(buc[a[x]]==1){
		pos[a[x]]=top+1;
		stk[++top]=a[x];
	}
	else if(buc[a[x]]==2){
	//	cout<<x<<" ";
		if(!pos[a[x]]) return;
		pos[stk[top]]=pos[a[x]];
		stk[pos[a[x]]]=stk[top];
	//	swap(stk[pos[a[x]]],stk[top]);
		top--;
		pos[a[x]]=0;
	}
}

inline void del(int x){
	buc[a[x]]--;
	if(buc[a[x]]==1){
		pos[a[x]]=top+1;
		stk[++top]=a[x];
	}
	else if(buc[a[x]]==0){
		if(!pos[a[x]]) return;
		pos[stk[top]]=pos[a[x]];
	//	swap(stk[pos[a[x]]],stk[top]);
		stk[pos[a[x]]]=stk[top];
		top--;
		pos[a[x]]=0;	
	}
}

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
    r=0;bool w=0; char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
    r=w?-r:r;
}

inline void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int main(){
	ios::sync_with_stdio(false);
	read(n);
	for(register int i=1;i<=n;++i) read(a[i]);
	read(m);
	T=2000;
	for(register int i=1;i<=m;++i){
		read(q[i].l);read(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	
	int x=1,y=0;
	for(register int i=1;i<=m;++i){
		int qx=q[i].l,qy=q[i].r;
		while(x>qx){
			x--;
			add(x);
		}
		while(y<qy){
			y++;
			add(y);
		}
		while(x<qx){
			del(x);
			x++;
		}
		while(y>qy){
			del(y);
			y--;
		}
	//	cout<<q[i].id<<" "<<top<<"\n";
		ansi[q[i].id]=stk[top];
	}
    if(m<=10){
        for(int i=1;i<=m;++i){
            write(ansi[i]);
            putchar('\n');
        }
        return 0;
    }
    #pragma unroll 10
	for(register int i=1;i<=m;++i){
        write(ansi[i]);
        putchar('\n');
    }
	return 0;
}