rt

#pragma GCC optimize("Ofast")
#pragma GCC optimize (3)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct node {
	int l, r, id;
} s[N];
static int c[N], ans[N], cnt[N], pos[N], t[N], now[N];
static int top, slen, n, m, l = 1, r = 0;
inline int read() {
	register int t = 1, a = 0;
	register char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') t = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0')
		a = a * 10 + ch - '0', ch = getchar();
	return a * t;
}
inline void write(long long x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline bool cmp(node x, node y) {
	if (pos[x.l] != pos[y.l]) return x.l < y.l;
	return (pos[x.l] & 1) ? x.r < y.r : x.r > y.r;
}
inline void sadd(int x) {
	now[++ top] = x, t[x] = top;
}
inline void sdel(int x) {
	now[top] ^= now[t[x]] ^= now[top] ^= now[t[x]];
	t[now[t[x]]] = t[x], -- top;
}
inline void add(int x) {
	if ((++ cnt[x]) == 1) sadd(x);
	else if (cnt[x] == 2) sdel(x);
}
inline void del(int x) {
	if ((-- cnt[x]) == 1) sadd(x);
	else if (!cnt[x]) sdel(x);
}
int main() {
	n = read(), slen = sqrt(n);
	for (register int i = 1; i <= n; i ++)
		c[i] = read(), pos[i] = (i - 1) / slen + 1;
	m = read();
	for (register int i = 1; i <= m; i ++)
		s[i].l = read(), s[i].r = read(), s[i].id = i;
	sort(s + 1, s + 1 + m, cmp);
	for (register int i = 1; i <= m; i ++) {
		while (l < s[i].l) del(c[l ++]);
		while (r > s[i].r) del(c[r --]);
		while (l > s[i].l) add(c[-- l]);
		while (r < s[i].r) add(c[++ r]);
		ans[s[i].id] = now[top];
	}
	for (register int i = 1; i <= m; i ++)
		write(ans[i]), putchar('\n');
	return 0;
}

验证码 wa37 祭。