#include <fstream>
#include <algorithm>
#pragma GCC optimize("O4,unroll-loops")
using namespace std;

#define int long long
#define ll int
#define u unsigned

int n, q, v[100005], cer, nr, ub, lb;

int upperbound(int x) {
    int l = 0, h = n-1, mid;
    while (l < h) {
        mid = (l+h)/2;
        if (v[mid] > x) h = mid;
        else l = mid+1;
    }
    return h;
}

int lowerbound(int x) {
    int l = 0, h = n-1, mid;
    while (l < h) {
        mid = (l+h)/2;
        if (v[mid] >= x) h = mid;
        else l = mid+1;
    }
    return h;
}

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

signed main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v, v+n);
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> cer >> nr;
        if (cer == 0) {
            ub = upperbound(nr);
            cout << v[ub-1]+1 << '\n';
        } else if (cer == 1) {
            ub = upperbound(nr);
            cout << v[ub-1]+1 << '\n';
        } else if (cer == 2) {
            lb = lowerbound(nr);
            cout << v[lb-1]+1 << '\n';
        }
    }
}