#include <bits/stdc++.h>

using namespace std;

int v[100005];

int findRightPos(int x, int n) {
    // Cautam cea mai din dreapta poz <= x
    int left = 1;
    int right = n;
    while (left < right) {
        // cat timp nu suntem la o singura valoare
        int middle = (left + right) / 2;
        // imi iau mijlocul intervalului
        // o sa ne uitam la optiunea [left, middle], [middle + 1, right]

        if (v[middle + 1] <= x) {
            // daca am cel putin o valoare <= x in dreapta
            // atunci mergem pe intervalul [middle + 1, right]
            left = middle + 1;
        } else {
            // daca nu am nici macar o valoare <= x in dreapta
            // atunci suntem obligati sa mergem pe stanga adica [left, middle]
            right = middle;
        }
    }
    // cand am ajuns sa avem o singura pozitie in interval - adica left == right
    // o returnam
    return left;
}

int findLeftPos(int x, int n) {
    // Cautam cea mai din stanha poz >= x
    int left = 1;
    int right = n;
    while (left < right) {
        // cat timp nu suntem la o singura valoare
        int middle = (left + right) / 2;
        // imi iau mijlocul intervalului
        // o sa ne uitam la optiunea [left, middle], [middle + 1, right]

        if (v[middle] >= x) {
            // daca am cel putin o valoare >= x in stanga
            // atunci mergem pe intervalul [left, middle]
            right = middle;
        } else {
            // daca nu am nici macar o valoare >= x in stanga
            // atunci suntem obligati sa mergem pe stanga adica [middle + 1, right]
            left = middle + 1;
        }
    }
    // cand am ajuns sa avem o singura pozitie in interval - adica left == right
    // o returnam
    return left;
}

int main() {
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    int n, m;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    fin >> m;
    for (int i = 1; i <= m; ++i) {
        int type, x;
        fin >> type >> x;
        if (type == 0) {
            // caut cea mai din dreapta poz a lui x sau -1 daca nu exista
            // caut cea mai din dreapta poz <= x
            int poz = findRightPos(x, n);
            // daca v[poz] != x, atunci -1, altfel poz
            if (v[poz] != x) {
                fout << -1 << '\n';
            } else {
                fout << poz << '\n';
            }
        } else if (type == 1) {
            // caut cea mai din dreapta poz <= x
            int poz = findRightPos(x, n);
            fout << poz << '\n';
        } else {
            // caut cea mai din stanga poz >= x
            int poz = findLeftPos(x, n);
            fout << poz << '\n';
        }
    }
    return 0;
}