#include <iostream>
#include <fstream>
#include <vector>

#define pb push_back

using namespace std;

vector<int> n;

int uppB(vector<int> &n, int key) {
    int low = 0, high = n.size() - 1;
    while (low < high) {
        int mid = low + (1 + high - low) / 2;
        if (n[mid] == key) low = mid;
        else if (n[mid] < key) low = 1 + mid;
        else high = mid - 1;
    }
    return key == n[low] ? 1 + low : -1;
}

int uppLB(vector<int> &n, int key) {
    int low = 0, high = n.size() - 1;
    while (low < high) {
        int mid = low + (1 + high - low) / 2;
        if (n[mid] <= key) low = mid;
        else high = mid - 1;
    }
    return 1 + low;
}

int lowB(vector<int> &n, int key) {
    int low = 0, high = n.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (key <= n[mid]) high = mid;
        else low = 1 + mid;
    }
    return 1 + low;
}

int main() {
    ifstream in("cautbin.in");
    cin.rdbuf(in.rdbuf());
    fstream out("cautbin.out");
    cout.rdbuf(out.rdbuf());

    int N, _n;
    cin >> N;
    for (int it = 0; it < N; ++it) {    
        cin >> _n;
        n.pb(_n);
    }
    int M, type, key;
    cin >> M;
    for (int it = 0; it < M; ++it) {
        cin >> type >> key;
        switch(type) {
            case 0: {
                cout << uppB(n, key) << endl;
                break;
            }
            case 1: {
                cout << uppLB(n, key) << endl;
                break;
            }
            case 2: {
                cout << lowB(n, key) << endl;
                break;
            }
        }
    }

    return 0;
}