/*
 * Lefter Sergiu - 09/07/2024
 */
#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int N = 1e5;

int v[N], n;

int caut_bin_0(int x) {
    // caut binar cel mai mare i cu proprietatea: v[i] <= x
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] <= x) { // daca m are proprietatea => m este un posibil rezultat final
            rez = m;
            st = m + 1; // caut in dreapta lui m ceva "mai bun"
        } else {
            dr = m - 1;
        }
    }
    if (rez == -1 || v[rez] != x) {
        return -1;
    }
    return rez + 1; // am indexat de la 0
}

int caut_bin_1(int x) {
    // caut binar cel mai mare i cu proprietatea: v[i] <= x
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] <= x) { // daca m are proprietatea => m este un posibil rezultat final
            rez = m;
            st = m + 1; // caut in dreapta lui m ceva "mai bun"
        } else {
            dr = m - 1;
        }
    }
    return rez + 1; // am indexat de la 0
}

int caut_bin_2(int x) {
    // caut binar cel mai mic i cu proprietatea: v[i] >= x
    int st = 0, dr = n - 1, rez = n;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] >= x) { // daca m are proprietatea => m este un posibil rezultat final
            rez = m;
            dr = m - 1; // caut in stanga lui m ceva "mai bun"
        } else {
            st = m + 1;
        }
    }
    return rez + 1; // am indexat de la 0
}

int main() {
    in >> n;
    for (int i = 0; i < n; i++) {
        in >> v[i];
    }
    int m;
    in >> m;
    for (int i = 0; i < m; i++) {
        int tip, x;
        in >> tip >> x;
        if (tip == 0) {
            out << caut_bin_0(x) << "\n";
        } else if (tip == 1) {
            out << caut_bin_1(x) << "\n";
        } else {
            out << caut_bin_2(x) << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}