#include <fstream>
#include <vector>
#include <string>

using namespace std;

const string IN_FILE = "cautbin.in";
const string OUT_FILE = "cautbin.out";

int findFirstGreaterThan(const vector<int>& values, const int x) {
    int left = 0, right = int(values.size()) - 1;
    int where = int(values.size()) - 1;
    while (left <= right) {
        const int middle = left + (right - left) / 2;
        if (values[middle] <= x) {
            where = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return where + 1;
}

int findLastLessThan(const vector<int>& values, const int x) {
    int left = 0, right = int(values.size()) - 1, where = 0;
    while (left <= right) {
        const int middle = left + (right - left) / 2;
        if (values[middle] >= x) {
            where = middle;
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return where - 1;
}

int findLast(const vector<int>& values, const int x) {
    const int where = findFirstGreaterThan(values, x);
    return where > 0 && values[where - 1] == x ? where - 1 : -1;
}

int main() {
    ifstream in(IN_FILE);
    ofstream out(OUT_FILE);
    int n;
    in >> n;
    auto values = vector<int>(n);
    for (int i = 0; i < n; i++) {
        in >> values[i];
    }
    int m;
    in >> m;
    for (int i = 0; i < m; i++) {
        int type, x;
        in >> type >> x;
        if (type == 0) {
            out << findLast(values, x) + 1 << "\n";
        } else if (type == 1) {
            out << findFirstGreaterThan(values, x) + 1 - 1 << "\n";
        } else {
            out << findLastLessThan(values, x) + 1 + 1 << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}