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

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int i, j, n, m, tip, nr, v[100002];

int binarySearch0() {
    int hi = n;
    int lo = 1, mid;
    while (hi >= lo) {
        mid = lo + (hi - lo) / 2;
        if (v[mid] <= nr)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    if (v[mid] > nr)
        --mid;
    if (v[mid] == nr)
        return mid;
    return -1;
}

int binarySearch1() {
    int hi = n;
    int lo = 1, mid;
    while (hi > lo) {
        mid = lo + (hi - lo) / 2;
        if (v[mid] <= nr)
            lo = mid + 1;
        else
            hi = mid;
    }
    if (v[mid] > nr)
        --mid;
    return mid;
}
int binarySearch2() {
    int hi = n;
    int lo = 1, mid;
    while (hi > lo) {
        mid = lo + (hi - lo) / 2;
        if (v[mid] < nr)
            lo = mid + 1;
        else
            hi = mid;
    }
    if (v[mid] < nr)
        ++mid;
    return mid;
}

int main() {
    fin >> n;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (i = 0; i < m; ++i) {
        fin >> tip >> nr;
        if (tip == 0)
            fout << binarySearch0() << '\n';
        else {
            if (tip == 1)
                fout << binarySearch1() << '\n';
            else fout << binarySearch2() << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}