#include <iostream>
#include <fstream>
#define NMAX 100001

using namespace std;

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

int v[NMAX], n, m;
int binary(int op, int x, int y, int val);

int main() {

    int op, val;
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> v[i];

    for (in >> m; m; --m) {

        in >> op >> val;
        out << binary(op, 1, n, val) << "\n";
    }

    in.close();
    out.close();
    return 0;
}

int binary(int op, int x, int y, int val) {

    while (x <= y) {

        int m = x + (y - x) / 2;

        if (op == 0)
        if (v[m] == val && (m == y || v[m + 1] > val))
            return m;
        if (op == 1)
        if (v[m] <= val && (m == y || v[m + 1] > val))
            return m;
        if (op == 2)
        if (v[m] >= val && (m == 1 || v[m - 1] < val))
            return m;

        if (op == 0 || op == 1) {

            if (v[m] <= val)
                x = m + 1;
            else
                y = m - 1;
        } else {
            if (v[m] >= val)
                y = m - 1;
            else
                x = m + 1;
        }
    }
    return -1;
}