#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int B = sqrt(n);
    vector<int> a(n + 5);
    map<int, bool> vis;
    int mx(0), piv(0);
    for (int i = 1; i <= n; i++) {cin >> a[i]; vis[a[i]] = 1; mx = max(a[i], mx);}
    for (int i = 0; i <= mx + 1; i++) {
        if (!vis[i]) {
            // cout << "i = " << i << '\n';
            piv = i;
            break;
        }
    }
    int B_ = sqrt(piv);
    // cout << "B_ = " << B_ << '\n';
    map<int, int> vis_;
    vector<int> bull(piv / B_ + 5);
    int q; cin >> q;
    vector<pii> query(q + 5);
    for (int i = 1; i <= q; i++) {
        cin >> query[i].fi >> query[i].se;
    }
    vector<int> order(q + 5);
    iota(order.begin() + 1, order.begin() + 1 + q, 1);
    // for (int i = 1; i <= n; i++) {
    //     cout << "order[" << i << "] = " << order[i] << '\n';
    // }
    auto cmp = [&](int a_, int b_) {
        pii a = query[a_];
        pii b = query[b_];
        int temp = a.fi / B;
        int temp_ = (a.fi / B < b.fi / B);
        int temp__ = ((a.fi / B == b.fi / B) && ((temp % 2 == 0) ? a.se < b.se : a.se > b.se));
        int temp___ = (a.fi / B == b.fi / B);
        int temp____  = (temp % 2 == 0) ? a.se < b.se : a.se > b.se;
        // cout << "query[" << a_ << "] = " << query[a_].fi / B << '\n';
        // cout << "query[" << b_ << "] = " << query[b_].fi / B << '\n';
        // cout << "temp_ = " << temp_ << '\n';
        // cout << "temp__ = " << temp__ << '\n';
        // cout << "temp___ = " << temp___ << '\n';
        // cout << "temp____ = " << temp____ << '\n';
        // cout << "total = " << ((a.fi / B < b.fi / B) || ((a.fi / B == b.fi / B) && ((temp % 2 == 0) ? a.se < b.se : a.se > b.se))) << "这里后面是" << '\n';
        // cout << "or = " << temp_
        // cout << '\n';
        // cout << '\n';
        return (a.fi / B < b.fi / B) || ((a.fi / B == b.fi / B) && ((temp % 2 == 0) ? a.se < b.se : a.se > b.se)); 
    };
    sort(order.begin() + 1, order.begin() + 1 + q, cmp);
    auto remove = [&](int pos) {
        if (a[pos] > piv) return;
        vis_[a[pos]]--;
        bull[a[pos] / B_]--;
    };
    auto add = [&](int pos) {
        if (a[pos] > piv) return;
        vis_[a[pos]]++;
        bull[a[pos] / B_]++;
    };
    int l = 1;
    int r = 1;
    add(1);
    vector<int> ans(q + 5);
    for (int i = 1; i <= q; i++) {
        if (B_ == 0) {ans[order[i]] = 0; continue;}
        // cout << order[i] << " : " << query[order[i]].fi << ' ' << query[order[i]].se << '\n';
        while (l < query[order[i]].fi) remove(l++);
        while (l > query[order[i]].fi) add(--l);
        while (r < query[order[i]].se) add(++r);
        while (r > query[order[i]].se) remove(r--);
        int beg = 0;
        for (int j = 0; j <= piv / B_; j++) {
            // cout << "bull[" << j << "] = " << bull[j] << '\n';
            if (j == piv / B_) {
                for (int k = beg; k <= piv; k++) {
                    if (!vis_[k]) {
                        ans[order[i]] = k;
                        goto end;
                    }
                }
            }
            else {
                if (bull[j] != B_) {
                    for (int k = beg; k <= beg + B_ - 1; k++) {
                        if (!vis_[k]) {
                            ans[order[i]] = k;
                            goto end;
                        }
                    }
                }
            }
            beg += B_;
        }
        end:;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}
/*
6
5 3 0 1 2 3
i = 4
B_ = 2
6
5 2
1 1
5 2
1 1
5 2 
1 1
*/