#include <iostream>
#include <fstream>

#define M 100010

using namespace std;

int v[M];

int rezolvare0 (int st, int dr, int a) {
    int mid;
    while (st <= dr) {
        mid = st + (dr - st) / 2;
        if (v[mid] <= a)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    mid = st + (dr - st) / 2;

    if (v[mid] > a) mid --;
    if (v[mid] == a)
        return mid;
    return -1;
}

int rezolvare1 (int st, int dr, int a) {
    int mid;

    while (st < dr){
        mid = st + (dr - st) / 2;
        if (v[mid] <= a)
            st = mid + 1;
        else
            dr = mid;
    }

    mid = st + (dr - st) / 2;
    if (v[mid] > a)
       -- mid;
    return mid;
}

int rezolvare2 (int st, int dr, int a) {
    int mid;

    while (st < dr) {
        mid = st + (dr - st) / 2;
        if (v[mid] < a)
            st = mid + 1;
        else
            dr = mid;
    }

    mid = st + (dr - st) / 2;
    if (v[mid] < a)
       ++ mid;
    return mid;
}

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

    int n, m, q, a, i;
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i];

    fin >> m;

    for (i=1; i<=m; i++) {
        fin >> q >> a;
        if ( q == 0 )
            fout << rezolvare0 (1, n, a) << '\n';
        if ( q == 1 )
            fout << rezolvare1 (1, n, a) << '\n';
        if ( q == 2 )
            fout << rezolvare2 (1, n, a) << '\n';
    }
    return 0;
}