#include <bits/stdc++.h>
using namespace std;

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

const int MAX_LENGTH = 100000;
int v[MAX_LENGTH + 1];

int main() {
    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 q, x;
        fin >> q >> x;
        int left = 1, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x > v[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        while ((q < 2 && v[left + 1] == x) || (q == 2 && v[left] < x)) {
            ++left;
        }
        while (q == 1 && v[left] > x) {
            --left;
        }
        if (q < 1 && v[left] != x) {
            left = -1;
        }
        fout << left << '\n';
    }
    return 0;
}