#include <iostream>
#include <fstream>
using namespace std;

#define N 100010
int v[N];

int bsearch0(int left, int right, int value) {
    int middle;
    while (left <= right) {
        middle = (left + right) / 2;
        if (v[middle] <= value)
            left = middle + 1;
        else
            right = middle - 1;
    }
    middle = (left + right) / 2;
    if (v[middle] > value) middle--;
    if (v[middle] == value)
        return middle;
    return -1;
}

int bsearch1(int left, int right, int value) {
    int middle;
    while (left < right) {
        middle = (left + right) / 2;
        if (v[middle] <= value)
            left = middle + 1;
        else
            right = middle;
    }
    middle = (left + right) / 2;
    if (v[middle] > value)
        middle--;
    return middle;
}

int bsearch2(int left, int right, int value) {
    int middle;
    while (left < right) {
        middle = (left + right) / 2;
        if (v[middle] < value)
            left = middle + 1;
        else
            right = middle;
    }
    middle = (left + right) / 2;
    if (v[middle] < value)
        middle++;
    return middle;
}

int main() {
    int i, n, m, tip, val;
    
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    cin >> n;
    for (i = 1; i <= n; ++i)
        cin >> v[i];

    cin >> m;

    while (m--) {
        cin >> tip >> val;
        if (tip == 0)
            cout << bsearch0(1, n, val) << endl;
        if (tip == 1)
            cout << bsearch1(1, n, val) << endl;
        if (tip == 2)
            cout << bsearch2(1, n, val) << endl;
    }



    return 0;
}