#include <fstream>

using namespace std;

const int NMAX = 100001;
const int MMAX = 100001;

const char IN[] = "cautbin.in";
const char OUT[] = "cautbin.out";

ifstream fin(IN);
ofstream fout(OUT);

int N, M;
int A[NMAX];

void FirstSearch(int val) {
    int step, i;
    for(step = 1; step < N; step <<= 1);

    for(i = 0; step; step >>= 1)
        if(i + step <= N && A[i + step] <= val)
            i += step;

    if(A[i] != val) i = -1;

    fout << i << '\n';
}

void SecondSearch(int val) {
    int step, i;
    for(step = 1; step < N; step <<= 1);

    for(i = 0; step; step >>= 1)
        if(i + step <= N && A[i + step] <= val)
            i += step;

    fout << i << '\n';
}

void ThirdSearch(int val) {
    int step, pas;
    for(step = 1; step < N; step <<= 1);

    pas = step;
    if(pas > N) pas >>= 1;
    if(A[pas] < val) pas = N;

    for(; step; step >>= 1)
        if(pas - step <= N && pas >= step && A[pas - step] >= val)
            pas -= step;

    fout << pas << '\n';
}

int main() {
    int i, val, cod;

    fin >> N;
    for(i = 1; i <= N; ++i)
        fin >> A[i];

    fin >> M;
    for(i = 1; i <= M; ++i) {
        fin >> cod >> val;

        switch(cod) {
            case 0: FirstSearch(val); break;
            case 1: SecondSearch(val); break;
            case 2: ThirdSearch(val); break;
        }
    }

    return 0;
}