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

int v[100005];

int binarySearchRight(int n, int x) {
    int left = 1, right = n;

    while (left < right) {
        int middle = (left + right) / 2;

        // deoarece vreau sa merg cat mai in dreapta, ma voi uita la intervalul [middle + 1, right]
        // daca [middle + 1, right] nu este bun, merg pe [left, middle]
        if (v[middle + 1] <= x) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }

    return left;
}

int binarySearchLeft(int n, int x) {
    int left = 1, right = n;

    while (left < right) {
        int middle = (left + right) / 2;

        // deoarece vreau sa merg cat mai in stanga, atunci ma voi uita la intervalul [left, middle] prima data
        if (x <= v[middle]) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }

    return left;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int type, x;
        cin >> type >> x;
        if (type == 0) {
            int pos = binarySearchRight(n, x);
            if (v[pos] != x) {
                cout << -1 << '\n';
            } else {
                cout << pos << '\n';
            }
        } else if (type == 1) {
            cout << binarySearchRight(n, x) << '\n';
        } else {
            cout << binarySearchLeft(n, x) << '\n';
        }
    }
    return 0;
}