求调

#include<bits/stdc++.h>
using namespace std;
int arr[500100];
struct node{
	int l, r, idx, ans;
}que[500100];
int block;
bool cmp(node x, node y) {
	if(x.l / block  == y.l / block) {
		return x.r < y.r;
	}
	return x.l / block < y.l / block;
}
stack<int> sta;
bool is[500100];
int ti[500100];
void add(int index) {
	index = arr[index];
	ti[index] ++;
	if(ti[index] == 1) {
		if(is[index]) {
			is[index] = 0;
			return;
		}
		sta.push(index);
	}
    if(ti[index] == 2) {
        is[index] = 1;
    }
}
void del(int index) {
	index = arr[index];
	ti[index] --;
	if(ti[index] == 0) {
		is[index] = 1;
	}
}
bool cmp2(node x, node y) {
	return x.idx < y.idx;
}
int main() {
	int n, q; cin >> n;
	for(int i=1; i<=n; ++i) {
		cin >> arr[i];
	}
    cin>>q;
	for(int i=1; i<=q; ++i) {
		cin >> que[i].l >> que[i].r; que[i].idx = i;
	}
	block = sqrt(n);
	sort(que+1,que+1+q,cmp);
	int l = 1, r = 0;
	for(int i=1; i<=q; ++i) {
		int left = que[i].l, right = que[i].r;
		while(r>right) del(r--);
		while(r<right) add(++r);
		while(l<left) add(++l);
		while(l>left) del(l--);
		while(!sta.empty() && is[sta.top()]) {
			is[sta.top()] = 0;
			sta.pop();
		}
		if(sta.empty()) {
			que[i].ans = 0;
		} else {
			que[i].ans = sta.top();
		}
	}
	sort(que+1,que+1+q,cmp2);
	for(int i=1; i<=q; ++i)cout << que[i].ans<<endl;
	return 0;
}