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

#include <cstdio>
#include <climits>
#include <cstdint>

static char ibuf[(1 << 22) + 1];
static char obuf[(1 << 22)];
static char *ip = ibuf, *op = obuf;

struct FastIO {
    FastIO() {
        freopen("cautbin.in", "r", stdin);
        freopen("cautbin.out", "w", stdout);
        size_t sz = fread(ibuf, 1, (1 << 22), stdin);
        ibuf[sz] = '\0';
    }
    ~FastIO() {
        fwrite(obuf, 1, (size_t)(op - obuf), stdout);
    }
} fastio;

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

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

inline void writeInt(int x) {
    if (x < 0) {
        *op++ = '-';
        x = -x;
    }

    char buf[12];
    int len = 0;

    if (x == 0) {
        buf[len++] = '0';
    } else {
        while (x >= 100) {
            int r = x % 100;
            buf[len++] = digit_pairs[r * 2 + 1];
            buf[len++] = digit_pairs[r * 2];
            x /= 100;
        }
        if (x >= 10) {
            buf[len++] = digit_pairs[x * 2 + 1];
            buf[len++] = digit_pairs[x * 2];
        } else {
            buf[len++] = char('0' + x);
        }
    }

    while (len) *op++ = buf[--len];
    *op++ = '\n';
}

constexpr int MAXN = 100000;
constexpr int MAXM = 100000;
constexpr int TOPBIT = 16;
constexpr int LIM = (1 << (TOPBIT + 1)) - 1;   // 131071
constexpr int K = 8;

alignas(64) static int v[LIM + 1];
static uint8_t qtype[MAXM + 1];
static int qval[MAXM + 1];
static int ans[MAXM + 1];
static int bsl_idx[MAXM + 1];
static int bsr_idx[MAXM + 1];

static int n, m;

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;
    }
}

template<int bit>
__attribute__((always_inline))
inline void bsr8(const int* __restrict__ xs, int* __restrict__ ps) {
    if constexpr (bit >= 0) {
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) {
            int next = ps[j] + (1 << bit);
            if (v[next] <= xs[j]) ps[j] = next;
        }
        bsr8<bit - 1>(xs, ps);
    }
}

template<int bit>
__attribute__((always_inline))
inline void bsl8(const int* __restrict__ xs, int* __restrict__ ps) {
    if constexpr (bit >= 0) {
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) {
            int next = ps[j] + (1 << bit);
            if (v[next] < xs[j]) ps[j] = next;
        }
        bsl8<bit - 1>(xs, ps);
    }
}

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

    int bsl_cnt = 0;
    int bsr_cnt = 0;

    for (int i = 0; i < m; ++i) {
        int t = readInt();
        int x = readInt();
        qtype[i] = (uint8_t)t;
        qval[i] = x;

        if (t != 1) bsl_idx[bsl_cnt++] = i;
        if (t == 1) bsr_idx[bsr_cnt++] = i;
    }

    int i = 0;
    for (; i + K <= bsl_cnt; i += K) {
        int xs[K], ps[K] = {};
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) xs[j] = qval[bsl_idx[i + j]];
        bsl8<TOPBIT>(xs, ps);
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) ans[bsl_idx[i + j]] = ps[j] + 1;
    }
    for (; i < bsl_cnt; ++i) {
        int qi = bsl_idx[i];
        ans[qi] = bsl1<TOPBIT>(qval[qi]);
    }

    for (int k = 0; k < bsl_cnt; ++k) {
        int qi = bsl_idx[k];
        if (qtype[qi] == 0) {
            int lb = ans[qi];
            if (v[lb] == qval[qi]) {
                bsr_idx[bsr_cnt++] = qi;
            } else {
                ans[qi] = -1;
            }
        }
    }

    i = 0;
    for (; i + K <= bsr_cnt; i += K) {
        int xs[K], ps[K] = {};
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) xs[j] = qval[bsr_idx[i + j]];
        bsr8<TOPBIT>(xs, ps);
        #pragma GCC unroll 8
        for (int j = 0; j < K; ++j) ans[bsr_idx[i + j]] = ps[j];
    }
    for (; i < bsr_cnt; ++i) {
        int qi = bsr_idx[i];
        ans[qi] = bsr1<TOPBIT>(qval[qi]);
    }

    for (int i = 0; i < m; ++i) writeInt(ans[i]);
    return 0;
}