#include <iostream>
#include <fstream>

using namespace std;

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

int n, a[100005], m, op, val;

int main() {
    f >> n;
    for (int i = 1; i <= n; ++i)
        f >> a[i];
    f >> m;
    for (int i = 0; i < m; ++i) {
        f >> op >> val;
        if (op != 2) {
            int st = 1, dr = n, mij;
            while (st <= dr) {
                mij = (st + dr) / 2;
                if (a[mij] > val)
                    dr = mij - 1;
                else
                    st = mij+1;
            }
            if (op == 0) {
                if (a[dr] == val)
                    g << dr << '\n';
                else
                    g << -1<<'\n';
            } else if (op == 1)
                g << dr << '\n';
        } else {
            int st = 1, dr = n, mij;
            while (st <= dr) {
                mij = (st + dr) / 2;
                if (a[mij] >= val)
                    dr = mij - 1;
                else
                    st = mij+1;
            }
            g << st << '\n';
        }
    }
    return 0;
}