#include <fstream>
using namespace std;

// l excl; r incl
int last_le(int x, int v[], int l, int r) {
    do {
        int m = (l + r + 1) / 2;
        if (v[m] <= x)
            l = m;
        else
            r = m - 1;
    } while (l < r);
    return l; /* == r_i */
}
// l incl; r excl
int first_ge(int x, int v[], int l, int r) {
    do {
        int m = (l + r) / 2;
        if (v[m] < x)
            l = m + 1;
        else
            r = m;
    } while (l < r);
    return l; /* == r */
}

int main() {
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n, *v, m, op, x, tmp;
    in>>n;
    v = new int[m];
    for (int i = 0; i < n; i++)
        in>>v[i];
    in>>m;
    for (int i = 0; i < m; i++) {
        in>>op>>x;
        switch (op) {
        case 0: tmp = last_le(x, v, -1, n - 1);
                out<<(tmp >= 0 ? (v[tmp] == x ? tmp : -2) : -2) + 1<<endl; break;
        case 1: out<<last_le(x, v, -1, n - 1) + 1<<endl; break;
        case 2: out<<first_ge(x, v, 0, n) + 1<<endl; break;
        }
    }
    in.close();
    out.close();
    return 0;
}