#include <fstream>
#include <vector>

using namespace std;

int binary_search(const vector<int>& vec, int val)
{
    int lo = 0, hi = vec.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (vec[mid] <= val) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    int mid = lo + (hi - lo) / 2;
    if (vec[mid] > val)
        --mid;
    if (vec[mid] == val)
        return mid;

    return -1;
}

int lower_bound(const vector<int>& vec, int val)
{
    int lo = 0, hi = vec.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (vec[mid] <= val) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    int mid = lo + (hi - lo) / 2;
    if (vec[mid] > val)
        --mid;

    return mid;
}

int upper_bound(const vector<int>& vec, int val)
{
    int lo = 0, hi = vec.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (vec[mid] < val) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    int mid = lo + (hi - lo) / 2;
    if (vec[mid] < val)
        ++mid;

    return mid;
}

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;

    for (int i = 0; i < M; ++i) {
        int op, x;
        fin >> op >> x;

        if (op == 0) {
            fout << binary_search(vec, x) + 1 << "\n";
        } else if (op == 1) {
            fout << lower_bound(vec, x) + 1 << "\n";
        } else if (op == 2) {
            fout << upper_bound(vec, x) + 1 << "\n";
        }
    }

    return 0;
}