#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, i, j, x, y, m;
int v[111111];

inline int bin0 (int x, int lt, int rt) {

    int ret = -1;

    while (lt <= rt) {

        int mid = (lt + rt) / 2;
        if (v[mid] == x) {
            ret = mid;
            lt = mid + 1;
        } else if (v[mid] < x) {
            lt = mid + 1;
        } else {
            rt = mid - 1;
        }
    }

    return ret;
}

inline int bin1 (int x, int lt, int rt) {

    int ret = 0;

    while (lt <= rt) {
        int mid = (lt + rt ) / 2;

        if (v[mid] <= x) {
            ret = mid;
            lt = mid + 1;
        } else {
            rt = mid - 1;
        }
    }

    return ret;
}

inline int bin2 (int x, int lt, int rt) {

    int ret = 0;

    while (lt <= rt) {
        int mid = (lt + rt ) / 2;

        if (v[mid] >= x) {
            ret = mid;
            rt = mid - 1;
        } else {
            lt = mid + 1;
        }
    }

    return ret;
}

int main() {

    f >> n;
    for (i=1; i<=n; i++) {
        f >> v[i];
    }

    f >> m;
    for (i=1; i<=m; i++){
        f >> x >> y;
        if (x == 0) {
            g << bin0 (y, 1, n) << '\n';
        } else if (x == 1) {
            g << bin1 (y, 1, n) << '\n';
        } else if (x == 2) {
            g << bin2 (y, 1, n) << '\n';
        }
    }

}