#include <fstream>
using namespace std;

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

int a[100001], N;

// Tip 0: ultima apariție a lui x
int tip0(int x) {
    int st = 1, dr = N, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (a[mid] == x) {
            rasp = mid;
            st = mid + 1;         // mergem spre dreapta (căutăm ultima apariție)
        } else if (a[mid] < x) {
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return rasp;
}

// Tip 1: cea mai mare poziție i cu a[i] ≤ x
int tip1(int x) {
    int st = 1, dr = N, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (a[mid] <= x) {
            rasp = mid;
            st = mid + 1;         // mergem spre dreapta (căutăm valoare mai mare dar ≤ x)
        } else {
            dr = mid - 1;
        }
    }
    return rasp;
}

// Tip 2: cea mai mică poziție i cu a[i] ≥ x
int tip2(int x) {
    int st = 1, dr = N, rasp = -1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2;
        if (a[mid] >= x) {
            rasp = mid;
            dr = mid - 1;         // mergem spre stânga (căutăm prima apariție)
        } else {
            st = mid + 1;
        }
    }
    return rasp;
}

int main() {
    in >> N;
    for (int i = 1; i <= N; i++)
        in >> a[i];

    int M;
    in >> M;

    while (M--) {
        int tip, x;
        in >> tip >> x;

        if (tip == 0) out << tip0(x) << "\n";
        if (tip == 1) out << tip1(x) << "\n";
        if (tip == 2) out << tip2(x) << "\n";
    }

    return 0;
}