#include <fstream>
#include <vector>

using namespace std;

int UpperBound(const vector<int> &vec, int value)
{
    int pos = -1;
    int pow = (1 << 25);

    while (pow > 0) {
        int next_pos = pos + pow;
        pow >>= 1;

        if (next_pos < (int)vec.size() && vec[next_pos] <= value) {
            pos = next_pos;
        }
    }
    return pos;
}

int UpperBoundExact(const vector<int> &vec, int value)
{
    int pos = UpperBound(vec, value);
    return (0 <= pos && vec[pos] == value) ? pos : -2;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int n;
    fin >> n;

    vector<int> vec(n);
    for (auto &num : vec) {
        fin >> num;
    }

    int tests;
    fin >> tests;

    for (int i = 0; i < tests; i += 1) {
        int type, value;
        fin >> type >> value;

        switch (type) {
            case 0: fout << UpperBoundExact(vec, value) + 1 << "\n"; break;
            case 1: fout << UpperBound(vec, value) + 1 << "\n"; break;
            case 2: fout << UpperBound(vec, value - 1) + 2 << "\n"; break;
        }
    }
    return 0;
}