#include <cstdio>
#include <memory>

size_t b1(const std::unique_ptr<unsigned[]>& v, unsigned lookup, size_t startIndex, size_t len) {
    // primul element mai mare
    while (len) {
        size_t m = startIndex + len / 2;
        if (v[m] > lookup) {
            len = len / 2;
        } else {
            startIndex += len / 2 + 1;
            len = len - len / 2 - 1;
        }
    }
    return startIndex;
}

int b2(const std::unique_ptr<unsigned[]>& v, unsigned lookup, size_t startIndex, size_t len) {
    // primul element mai mare sau egal
    while (len) {
        size_t m = startIndex + len / 2;
        if (v[m] >= lookup) {
            len = len / 2;
        } else {
            startIndex += len / 2 + 1;
            len = len - len / 2 - 1;
        }
    }
    return startIndex;
}

int bb1(const std::unique_ptr<unsigned[]>& v, unsigned lookup, size_t startIndex, size_t len) {
    size_t firstHi = b1(v, lookup, startIndex, len);
    return firstHi - 1;
}

int b0(const std::unique_ptr<unsigned[]>& v, unsigned lookup, size_t startIndex, size_t len) {
    int result = bb1(v, lookup, startIndex, len);
    return v[result] == lookup ? result: -2;
};


using QueryFunc = int(const std::unique_ptr<unsigned[]>&, unsigned, size_t, size_t);


// 1 3 3 3 5 6 7
//
//

int main() {
    ::freopen("cautbin.in", "r", stdin);
    ::freopen("cautbin.out", "w", stdout);
    size_t n;
    scanf("%lu", &n);
    std::unique_ptr<unsigned[]> v(new unsigned[n]);

    for (size_t i = 0; i < n; ++i) {
        unsigned el;
        scanf("%u", v.get() + i);
    }

    QueryFunc* const queries[] = {b0, bb1, b2};

    size_t m, query;
    unsigned lookup;
    scanf("%lu", &m);
    for (size_t i = 0; i < m; ++i) {
        scanf("%lu %u", &query, &lookup);
        int res = queries[query](v, lookup, 0, n);
        printf("%d\n", res+1);
    }
    return 0;
}