#include <fstream>

using namespace std;

int binarySearch1(int v[], const int n, int x) {
    int left = 0, right = n - 1;
    int mid;
    bool found = false;

    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (v[mid] == x)
            found = true,
            left = mid + 1;
        else if (v[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if (found)
        return left;
    else
        return -1;
}

int binarySearch2(int v[], int n, int x) {
    int left = 0, right = n - 1;
    int mid;

    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (v[mid] <= x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}

int binarySearch3(int v[], int n, int x) {
    int left = 0, right = n - 1;
    int mid;

    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (x <= v[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right + 2;
}

int main(void) {
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    int n, i;
    in >> n;
    int v[n];
    for (i = 0; i < n; i++)
        in >> v[i];

    int m, op, x;
    in >> m;
    for (i = 0; i < m; i++) {
        in >> op >> x;
        switch (op) {
            case 0:
                out << binarySearch1(v, n, x) << '\n';
                break;
            case 1:
                out << binarySearch2(v, n, x) << '\n';
                break;
            case 2:
                out << binarySearch3(v, n, x) << '\n';
                break;
            default:
                break;
        }
    }

    in.close();
    out.close();
    return 0;
}