#include <bits/stdc++.h>
using namespace std;
// #define int long long
struct info {
    int lson, rson, num;
    info() : lson(0), rson(0), num(0) {}
    info(int lson, int rson, int num) : lson(lson), rson(rson), num(num) {}
};
struct segment_tree {
    int tot; vector<int> root;
    vector<info> tr;
    segment_tree(int n, int m) : tr(n * 30 + 5), tot(0), root(m + 5) {}
    int insert(int p, int l, int r, int x, int idx) {
        int q = ++tot;
        tr[q] = tr[p];
        if (l == r) {
            tr[q].num = idx;
            return q;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) tr[q].lson = insert(tr[p].lson, l, mid, x, idx);
        else tr[q].rson = insert(tr[p].rson, mid + 1, r, x, idx);
        tr[q].num = min(tr[tr[q].lson].num, tr[tr[q].rson].num);
        return q;
    }
    int query(int q, int p, int l, int r) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (tr[tr[p].lson].num < q) return query(q, tr[p].lson, l, mid);
        else return query(q, tr[p].rson, mid + 1, r);
    }
    void debug(int p, int l, int r, int idx) {
        cout << "tree " << idx << "'s " << l << ' ' << r << "has num = " << tr[p].num << '\n';
        // cout << "tree " << idx << "'s " << tr[p].lson << ' ' << tr[p].rson << "is " << tr[tr[p].lson].num << ' ' << tr[tr[p].rson].num << '\n';
        if (l == r) return;
        int mid = (l + r) >> 1;
        debug(tr[p].lson, l, mid, idx);
        debug(tr[p].rson, mid + 1, r, idx);
    }
};
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    map<int, bool> vis;
    vector<int> a(n + 5);
    int mx(0), piv(-1);
    for (int i = 1; i <= n; i++) {cin >> a[i]; vis[a[i]] = 1; mx = max(mx, a[i]);}
    for (int i = 0; i <= mx + 1; i++) {
        if (!vis[i]) {piv = i; break;}
    }
    segment_tree tree(piv + 2, n + 2);
    // cout << "piv = " << piv << '\n';
    for (int i = 1; i <= n; i++) {
        if (a[i] > piv) {tree.root[i] = tree.root[i - 1]; continue;}
        tree.root[i] = tree.insert(tree.root[i - 1], 0, piv, a[i], i);
        // tree.debug(tree.root[i], 0, piv, i);
    }
    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        if (piv == 0) cout << 0 << '\n';
        else {
            cout << tree.query(l, tree.root[r], 0, piv) << '\n';
        }
    }
    return 0;
}