#include <iostream>
#include <fstream>
using namespace std;

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

int n, v[100001], m, a, x, i;

int main() {
    in >> n;
    for (i = 1; i <= n; i++)
        in >> v[i];
    in >> m;
    for (i = 1; i <= m; i++) {
        in >> a >> x;
        if (a == 0) {
            int st = 1, dr = n;
            while (st <= dr) {
                int mij = (st + dr) / 2;
                if (v[mij] > x)
                    dr = mij - 1;
                else 
                    st = mij + 1;
            }
            st--;
            if (v[st] == x && st > 0)
                out << st << '\n';
            else 
                out << -1 << '\n';
        } else if (a == 1) {
            int st = 1, dr = n;
            while (st <= dr) {
                int mij = (st + dr) / 2;
                if (v[mij] > x)
                    dr = mij - 1;
                else 
                    st = mij + 1;
            }
            st--;
            out << st << '\n';
        } else {
            int st = 1, dr = n;
            while (st <= dr) {
                int mij = (st + dr) / 2;
                if (v[mij] >= x)
                    dr = mij - 1;
                else 
                    st = mij + 1;
            }
            out << st << '\n';
        }
    }
    return 0;
}