#include <bits/stdc++.h>

using namespace std;

int v[100005];

int binarySearch(int value, int n) {
    int pos = 0;

    // Iau toate puterile lui 2 de la 2^20 la 2^0
    // 1 << p = 2^p
    for (int p = 20; p >= 0; --p) {
        if (pos + (1 << p) <= n and v[pos + (1 << p)] <= value) {
            pos += (1 << p);
        }
    }

    return pos;
}
// cel mai mic element care indeplineste o cond === cel mai mare elem care NU indeplineste conditia + 1
// 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n, q;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int type, x;
        cin >> type >> x;
        if (type == 0) {
            int pos = binarySearch(x, n);
            if (v[pos] == x) {
                cout << pos;
            } else {
                cout << -1;
            }
        } else if (type == 1) {
            int pos = binarySearch(x, n);
            cout << pos;
        } else {
            int pos = binarySearch(x - 1, n);
            cout << pos + 1;
        }
        cout << '\n';
    }
    return 0;
}