#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#include <fstream>
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
#define MAXN 100001

int binaryBS (int type, int x, int v[MAXN], int n, int log_n) {
    if (type != 2) {
        int i;
        for (i = 1; log_n; log_n >>= 1) {
            if (i + log_n <= n && v[i + log_n] <= x)
                i += log_n;
        }
        if (type == 0 && v[i] != x)
            return -1;
        else
            return i;
    }
    int i;
    for (i = n; log_n; log_n >>= 1) {
        if (i - log_n > 0 && v[i - log_n] >= x)
            i -= log_n;
    }
    return i;
}
void solve() {
    int n, queries, logn;
    int v[MAXN];
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (logn = 1; logn <= n; logn <<= 1);

    fin >> queries;
    while (queries--) {
        int type, x;
        fin >> type >> x;
        fout << binaryBS (type, x, v, n, logn) << '\n';
    }

}
int main() {
    fin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    solve();
}