RE on #8

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 9;

#define gc getchar
inline int read() {
	int c = gc(), t = 1, n = 0;
	while(isspace(c)) { c = gc(); }
	if(c == '-') { t = -1, c = gc(); }
	while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

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

int st[N],top;

int n,m,len,l,r;
int a[N],sum[N],ans[N];

bool cmp(node u,node v) {
	if(u.bl != v.bl) return u.bl < v.bl;
	else {
		if(u.bl & 1) return u.r < v.r;
		else return u.r > v.r;
	}
}

inline void push(int p) {
	st[++top] = p;
}

inline void pop() {
	--top;
}

inline void add(int x) {
	++sum[a[x]];
	if(sum[a[x]] == 1) push(a[x]);
}

inline void del(int x) {
	--sum[a[x]];
	if(sum[a[x]] == 1) push(a[x]);
}

int main() {
	n = read(); len = pow(n,0.5);
	for(int i = 1;i <= n;i++) a[i] = read();
	m = read();
	for(int i = 1;i <= m;i++) {
		q[i].l = read(); q[i].r = read();
		q[i].id = i; q[i].bl = (q[i].l - 1) / len + 1;
	}
	sort(q + 1,q + m + 1,cmp);
	l = 1; r = 0;
	for(int i = 1;i <= m;i++) {
		while(l > q[i].l) add(--l);
		while(r < q[i].r) add(++r);
		while(l < q[i].l) del(l++);
		while(r > q[i].r) del(r--);
		while(top > 0 && sum[st[top]] != 1) pop();
		ans[q[i].id] = st[top];
	}
	for(int i = 1;i <= m;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}