#include <iostream>
#include <fstream>

using namespace std;

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

int v[100010];
int bsearch0(int dr, int st, int key) {
    int mj;
    while (dr <= st) {
        mj = (dr + st) / 2;
        if (v[mj] <= key)
            dr = mj + 1;
        else
            st = mj - 1;
    }
    mj = (dr + st) / 2;
    if (v[mj] > key) --mj;
    if (v[mj] == key)
        return mj;
    return -1;
}
int bsearch1(int dr, int st, int key) {
    int mj, n = st;
    while (dr < st) {
        mj = (dr + st) / 2;
        if (v[mj] <= key)
            dr = mj + 1;
        else
            st = mj;
    }
    mj = (dr + st) / 2;
    if (v[mj] > key)
        --mj;
    return mj;
}
int bsearch2(int dr, int st, int key) {
    int mj;
    while (dr < st) {
        mj = (dr + st) / 2;
        if (v[mj] < key)
            dr = mj + 1;
        else
            st = mj;
    }
    mj = (dr + st) / 2;
    if (v[mj] < key)
        ++ mj;
    return mj;
}
int main () {
    int n, m;
    fin >> n;
    for (int i = 1; i <= n; ++ i)
        fin >> v[i];
    fin >> m;
    while (m) {
        int tip, val;
        fin >> tip >> val;
        if (tip == 0)
            fout << bsearch0(1, n, val) << "\n";
        if (tip == 1)
            fout << bsearch1(1, n, val) << "\n";
        if (tip == 2)
            fout << bsearch2(1, n, val) << "\n";
        --m;
    }
}