one occ

#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 5e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, q, arr[maxn], occ[maxn];
int root[maxn], L[maxn * 80], R[maxn * 80], next_id = 1;
pii seg[maxn * 80];
void build(int id = 1, int l = 1, int r = n)
{
    if(l == r)
    {
        seg[id] = {mod, l};
        return;
    }
    int mid = (l + r) / 2;
    L[id] = ++next_id;
    R[id] = ++next_id;
    build(L[id], l, mid);
    build(R[id], mid + 1, r);
    seg[id] = min(seg[L[id]], seg[R[id]]);
}
int modify(int pos, int val, int id, int l = 1, int r = n)
{
    int new_id = ++next_id;
    if(l == r)
    {
        seg[new_id] = {val, l};
        return new_id;
    }
    int mid = (l + r) / 2;
    L[new_id] = L[id];
    R[new_id] = R[id];
    if(pos <= mid)
        L[new_id] = modify(pos, val, L[new_id], l, mid);
    else
        R[new_id] = modify(pos, val, R[new_id], mid + 1, r);
    seg[new_id] = min(seg[L[new_id]], seg[R[new_id]]);
    return new_id;
}
pii get(int x, int y, int id, int l = 1, int r = n)
{
    if(l > y || r < x) return {mod, mod};
    if(l >= x && r <= y) return seg[id];
    int mid = (l + r) / 2;
    return min(get(x, y, L[id], l, mid), get(x, y, R[id], mid + 1, r));
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    build();
    int prev_root = 1;
    for(int i = 1; i <= n; i++)
    {
        if(occ[arr[i]] != 0)
            prev_root = modify(occ[arr[i]], mod, prev_root);
        prev_root = modify(i, occ[arr[i]], prev_root);
        root[i] = prev_root;
        occ[arr[i]] = i;
    }
    cin >> q;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        pii p = get(l, r, root[r]);
        if(p.x < l)
            cout << arr[p.y] << "\n";
        else
            cout << "0\n";
    }
    return 0;
}