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

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

constexpr int IN_BUF  = 1 << 18;
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;

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

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

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 bsr_k(const int* __restrict__ xs, int* __restrict__ ps) {
    if constexpr (bit >= 0) {
        #pragma GCC unroll 16
        for (int j = 0; j < K; ++j) {
            int next = ps[j] + (1 << bit);
            if (v[next] <= xs[j]) ps[j] = next;
        }
        bsr_k<bit - 1>(xs, ps);
    }
}

template<int bit>
__attribute__((always_inline))
inline void bsl_k(const int* __restrict__ xs, int* __restrict__ ps) {
    if constexpr (bit >= 0) {
        #pragma GCC unroll 16
        for (int j = 0; j < K; ++j) {
            int next = ps[j] + (1 << bit);
            if (v[next] < xs[j]) ps[j] = next;
        }
        bsl_k<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;
    for (int i = 0; i < m; ++i) {
        int t = readInt();
        int x = readInt();
        qtype[i] = (uint8_t)t;
        qval[i] = x;
        if (t != 1) idx[bsl_cnt++] = i;
    }

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

    int bsr_cnt = 0;
    for (int i = 0; i < m; ++i) {
        if (qtype[i] == 1) {
            idx[bsr_cnt++] = i;
        } else if (qtype[i] == 0) {
            int lb = ans[i];
            if (v[lb] == qval[i]) idx[bsr_cnt++] = i;
            else ans[i] = -1;
        }
    }

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

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