#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int N, M;
vector<int> values;

int lBound(int x) {
    int step = 1;
    while (step < N) {
        step <<= 1;
    }
    int idx = -1;
    while (step) {
        if (idx + step < N && values[idx + step] <= x) {
            idx += step;
        }
        step >>= 1;
    }
    return idx;
}

int main() {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    cin >> N;
    values.assign(N, 0);
    for (int idx = 0; idx < N; idx++) {
        cin >> values[idx];
    }
    cin >> M;
    int type, x;
    for (int query = 0; query < M; query++) {
        cin >> type >> x;
        if (type == 0) {
            int lb = lBound(x);
            int result = (lb >= 0 && values[lb] == x) ? lb + 1 : -1;
            cout << result << "\n";
        } else if (type == 1) {
            cout << lBound(x) + 1 << "\n";
        } else {
            cout << lBound(x - 1) + 2 << "\n";
        }
    }
    return 0;
}