#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include <cstdio>

static char ibuf[1 << 20], obuf[1 << 20]; 
static char *ip = ibuf, *op = obuf;

struct FastIO {
    FastIO() {
        freopen("cautbin.in", "r", stdin);
        freopen("cautbin.out", "w", stdout);
        fread(ibuf, 1, sizeof ibuf, stdin);
    }
    ~FastIO() { fwrite(obuf, 1, op - obuf, stdout); }
} __fastio;

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

inline void writeInt(int x) {
    if (x < 0) { *op++ = '-'; x = -x; }
    char buf[12]; int len = 0;
    if (x == 0) buf[len++] = '0';
    while (x) { buf[len++] = '0' + x % 10; x /= 10; }
    while (len) *op++ = buf[--len];
    *op++ = '\n';
}

static int v[100001], n;

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

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

inline int bsr(int x) { return bsr_impl<16>(x, 0); }
inline int bsl(int x) { return bsl_impl<16>(x, 0); }
inline bool bs(int x) { int p = bsl(x); return p <= n && v[p] == x; }

int main() {
    n = readInt();
    for (int i = 1; i <= n; i++) v[i] = readInt();
    int m = readInt();
    while (m--) {
        int q = readInt(), a = readInt();
        if (q == 0) {
            if (bs(a)) writeInt(bsr(a));
            else writeInt(-1);
        } else if (q == 1)
            writeInt(bsr(a));
        else
            writeInt(bsl(a));
    }
}