#include <bits/stdc++.h>
using namespace std;

void read_input(vector<int> &elems, vector<pair<int, int>> &questions) {
    ifstream in("cautbin.in");
    int n, m;

    in >> n;
    for (int i = 0; i < n; i++) {
        int elem;
        in >> elem;
        elems.push_back(elem);
    }
    in >> m;

    for (int i = 0; i < m; i++) {
        int q, x;
        in >> q >> x;
        questions.push_back(make_pair(q, x));
    }
    in.close();
}

int solve(vector<int> &elems, pair<int, int> question) {
    if (question.first == 0) {
        int l = 0, r = elems.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (elems[mid] > question.second) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (elems[r] == question.second) {
            return r + 1;
        } else {
            return -1;
        }
    } else if (question.first == 1) {
        int l = 0, r = elems.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (elems[mid] > question.second) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;
    } else {
        int l = 0, r = elems.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (elems[mid] >= question.second) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r + 2;
    }
}

void print_output(vector<int> elems, vector<pair<int, int>> questions) {
    ofstream out("cautbin.out");

    for (auto question : questions) {
        out << solve(elems, question) << '\n';
    }
}

int main() {
    vector<int> elems;
    vector<pair<int, int>> questions;
    read_input(elems, questions);
    print_output(elems, questions);

    return 0;
}