#include <iostream>
#include <fstream>

using namespace std;

int caut0(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (x >= v[m])
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr) / 2;
    if (x < v[m]) m--;
    if (x == v[m]) return m;
    return -1;
}

int caut1(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st < dr) {
        m = (st + dr) / 2;
        if (x >= v[m])
            st = m + 1;
        else
            dr = m;
    }
    m = (st + dr) / 2;
    if (x < v[m])
        m--;
    return m;
}

int caut2(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st < dr) {
        m = (st + dr) / 2;
        if (x > v[m])
            st = m + 1;
        else
            dr = m;
    }

    m = (st + dr) / 2;
    if (x > v[m])
        m++;
    return m;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int v[100001], n, m, i, instr, x;
    fin >> n;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> instr >> x;
        if(instr == 0)
            fout << caut0(v, n, x) << "\n";
        else if(instr == 1)
            fout << caut1(v, n, x) << "\n";
        else
            fout << caut2(v, n, x) << "\n";
    }
}