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

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

int V[100001], N, M, i, j;

int cautBin(int V[], int N, int x) {
    int st, dr, m;
    st = 1; dr = N;
    while (st < dr) {
        m = (st + dr) / 2;
        if (V[m] == x) return m;
        if (V[m] > x) dr = m - 1;
        else st = m + 1;
    }
    return m;
}


int main() {
    f >> N;
    for (i = 1; i <= N; i++)
        f >> V[i];

    f >> M;
    int c, p;
    for (i = 1; i <= M; i++) {
        f >> c >> p;
        int poz = cautBin(V, N, p);
        if (c == 0) {
            if (V[poz] != p) g << "-1\n";
            else {
                while (V[++poz] == p);
                g << --poz << '\n';
            }
        }
        else if (c == 1) {
            if (V[poz] > p) g << poz << '\n';
            else if (V[poz] < p) g << poz + 1 << '\n';
            else {
                while (V[++poz] == p);
                g << --poz << '\n';
            }
        } else {
            if (V[poz] < p) g << poz << '\n';
            else if (V[poz] > p) g << poz - 1 << '\n';
            else {
                while (V[--poz] == p);
                g << ++poz << '\n';
            }

        }

    }
    return 0;
}