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

int N, M;
vector<int> values;

int lBound(int x) {
    // no[left] <= x < no[right]
    int left = -1, right = N;
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (values[mid] <= x) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
}

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;
}