#include <fstream>
#include <vector>

using namespace std;

int SmallerEqual(const vector<int> &vec, int x)
{
    int pow = (1 << 20);
    int pos = -1;

    while (pow > 0) {
        if (pos + pow < vec.size() && vec[pos + pow] <= x) {
            pos += pow;
        }
        pow >>= 1;
    }
    return pos;
}

int LastExact(const vector<int> &vec, int x)
{
    int pos = SmallerEqual(vec, x);
    return (pos > -1 && vec[pos] == x) ? pos : -1;
}

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

    int n;
    fin >> n;

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        fin >> vec[i];
    }

    int m;
    fin >> m;
    while (m--) {
        int r, x;
        fin >> r >> x;

        if (r == 0) {
            int pos = LastExact(vec, x);
            fout << (pos == -1 ? -1 : pos + 1) << "\n";
        } else if (r == 1) {
            fout << SmallerEqual(vec, x) + 1 << "\n";
        } else {
            fout << SmallerEqual(vec, x - 1) + 2 << "\n";
        }
    }

    return 0;
}