#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) {
            while (V[poz] >= p) poz--;
            if (V[poz+1] == p) g << poz+1 << '\n';
            else g << poz << '\n';
        }
        else {
            while (V[poz] <= p) poz++;
            if (V[poz-1] == p) g << poz-1 << '\n';
            else g << poz << '\n';
        }
    }
    return 0;
}