#include <iostream>
#include <fstream>

int command0(int *v, int len, int val) {
    int li = 0, ls = len - 1;
    int last = -1; //ultima valoare gasita


    while (li <= ls) {
        int lm = li + (ls - li) / 2;

        if (v[lm] == val) {
            last = lm;
            li = lm + 1;
        } else if (v[lm] < val) {
            ls = lm - 1;
        } else {
            li = lm + 1;
        }

    }

    if (last != -1) last++;

    return last;
}

int command1(int *v, int len, int val) {
    int li = 0, ls = len - 1;
    int last = -1; //ultima valoare gasita

    while (li <= ls) {
        int lm = li + (ls - li) / 2;

        if (v[lm] <= val) {
            last = lm;
            li = lm + 1;
        } else {
            ls = lm - 1;
        }

    }

    if (last != -1) last++;

    return last;
}

int command2(int *v, int len, int val) {

    int li = 0, ls = len - 1;
    int last = -1;

    while (li <= ls) {
        int lm = li + (ls - li) / 2;

        if (v[lm] >= val) {
            last = lm;
            ls = lm - 1;
        } else {
            li = lm + 1;
        }

    }

    if (last != -1) last++;

    return last;
}

int main() {

    std::ifstream fin("cautbin.in");
    std::ofstream fout("cautbin.out");

    int N, M;

    fin >> N;
    int v[N];

    for (int i = 0; i < N; i++) {
            fin >> v[i];
    }


    fin >> M;
    for (int i = 0; i < M; i++) {
        int cmd, val;
        fin >> cmd >> val;

        if (cmd == 0) {
           fout << command0(v, N, val) << '\n';
        } else if (cmd == 1) {
            fout << command1(v, N, val) << '\n';
        } else {
            fout << command2(v, N, val) << '\n';
        }
    }


    fin.close();
    fout.close();

    return 0;
}