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

int strict_upper_bound(const vector< int >& values, size_t size, int x) {
    int left = 1, right = (int)size;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (values[middle] <= x)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return (values[right] == x ? right : -1);
}

int non_strict_upper_bound(const vector< int >& values, size_t size, int x) {
    int left = 1, right = (int)size;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (values[middle] <= x)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return right;
}

int non_strict_lower_bound(const vector< int >& values, size_t size, int x) {
    int left = 1, right = (int)size;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (values[middle] < x)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return left;
}

void solve() {
    size_t size;
    cin >> size;
    vector< int > values(size + 2);
    for (int i = 1; i <= (int)size; ++i)
        cin >> values[i];

    int query_count;
    cin >> query_count;
    while (query_count--) {
        int operation, x;
        cin >> operation >> x;

        switch(operation) {
            case 0:
                cout << strict_upper_bound(values, size, x);
                break;
            case 1:
                cout << non_strict_upper_bound(values, size, x);
                break;
            case 2:
                cout << non_strict_lower_bound(values, size, x);
                break;
        }

        cout << '\n';
    }
}

int main() {
    assert(freopen("cautbin.in", "r", stdin));
    assert(freopen("cautbin.out", "w", stdout));
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}