#include <iostream>
#include <fstream>
#define N 100010
using namespace std;
int v[N];
int cmmpoz(int p, int u, int k) {
    int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= k)
            p = m + 1;
        else
            u = m - 1;
    }

    m = (p + u) / 2;

    if (v[m] > k) m--;
    if (v[m] == k)
        return m;
    return -1;
}

int cmmpoz2(int p, int u, int k) {
    int m;
    while (p < u) {
        m = (p + u) / 2;
        if (v[m] <= k)
            p = m + 1;
        else
            u = m;
    }
    m = (p + u) / 2;
    if (v[m] > k)
        m--;
    return m;
}
int cmmpoz3(int p, int u, int k) {
    int m;
    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < k)
            p = m + 1;
        else
            u = m;
    }
    m = (p + u) / 2;
    if (v[m] < k)
        m++;
    return m;
}
int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n, m;
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    while (m--) {
        int tip, val;
        fin >> tip >> val;
        if (tip == 0)
            fout << cmmpoz(1, n, val) << "\n";
        else if (tip == 1)
            fout << cmmpoz2(1, n, val) << "\n";
        else if (tip == 2)
            fout << cmmpoz3(1, n, val) << "\n";
    }
    return 0;
}