#pragma GCC optimize("O3,unroll-loops")

#include <cstdio>
#include <climits>

constexpr int TOPBIT = 16;
constexpr int LIM = (1 << (TOPBIT + 1)) - 1;

constexpr int IN_BUF  = 1 << 16;
constexpr int OUT_BUF = 1 << 16;

static char ibuf[IN_BUF + 1];
static char obuf[OUT_BUF];
static int ipos = 0, ilen = 0, opos = 0;

inline char gc() {
    if (ipos >= ilen) {
        ilen = (int)fread(ibuf, 1, IN_BUF, stdin);
        ipos = 0;
        if (ilen == 0) return 0;
    }
    return ibuf[ipos++];
}

inline int readInt() {
    char c = gc();
    while (c < '0') c = gc();
    int x = 0;
    while (c >= '0') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

inline void flushOut() {
    if (opos) { fwrite(obuf, 1, opos, stdout); opos = 0; }
}

static const char dp[201] =
    "00010203040506070809"
    "10111213141516171819"
    "20212223242526272829"
    "30313233343536373839"
    "40414243444546474849"
    "50515253545556575859"
    "60616263646566676869"
    "70717273747576777879"
    "80818283848586878889"
    "90919293949596979899";

inline void pc(char c) {
    if (opos == OUT_BUF) flushOut();
    obuf[opos++] = c;
}

inline void writeInt(int x) {
    if (x < 0) { pc('-'); x = -x; }
    char buf[12]; int len = 0;
    if (x == 0) buf[len++] = '0';
    else {
        while (x >= 100) { int r = x % 100; buf[len++] = dp[r*2+1]; buf[len++] = dp[r*2]; x /= 100; }
        if (x >= 10) { buf[len++] = dp[x*2+1]; buf[len++] = dp[x*2]; }
        else buf[len++] = char('0' + x);
    }
    while (len) pc(buf[--len]);
    pc('\n');
}

struct FastIOInit {
    FastIOInit() {
        freopen("cautbin.in", "r", stdin);
        freopen("cautbin.out", "w", stdout);
    }
    ~FastIOInit() { flushOut(); }
} fastio_init;

alignas(64) static int v[LIM + 1];

template<int bit>
__attribute__((always_inline)) inline int bsr1(int x, int pos = 0) {
    if constexpr (bit >= 0) {
        int next = pos + (1 << bit);
        if (v[next] <= x) pos = next;
        return bsr1<bit - 1>(x, pos);
    } else return pos;
}

template<int bit>
__attribute__((always_inline)) inline int bsl1(int x, int pos = 0) {
    if constexpr (bit >= 0) {
        int next = pos + (1 << bit);
        if (v[next] < x) pos = next;
        return bsl1<bit - 1>(x, pos);
    } else return pos + 1;
}

int main() {
    int n = readInt();
    for (int i = 1; i <= n; ++i) v[i] = readInt();
    for (int i = n + 1; i <= LIM; ++i) v[i] = INT_MAX;

    int m = readInt();
    while (m--) {
        int t = readInt(), x = readInt();
        if (t == 0) {
            int p = bsl1<TOPBIT>(x);
            writeInt(v[p] == x ? bsr1<TOPBIT>(x) : -1);
        } else if (t == 1) {
            writeInt(bsr1<TOPBIT>(x));
        } else {
            writeInt(bsl1<TOPBIT>(x));
        }
    }
    return 0;
}