#include <fstream>

using namespace std;

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

int N, query, key, i, M;
int v[100010];

int b_search(int query, int key) {
    int lb = 1, rb = N, pos = -1;

    while (lb <= rb) {
        int m = lb + (rb - lb)/2;

        if (key == v[m]) {
            pos = m;
            (query == 2) ? rb = m - 1 : lb = m + 1;
        } else if (key < v[m]) {
                if (query == 2) pos = m;
                rb = m - 1;
            } else if (key > v[m]){
                if (query == 1) pos = m;
                lb = m + 1;
            }
    }
    return pos;
}

int main()
{
    in >> N;
    for (i = 1; i <= N; ++i) {
        in >> v[i];
    }
    in >> M;
    for (i = 1; i <= M; ++i) {
        in >> query >> key;
        out << b_search(query, key) << '\n';
    }

    return 0;
}