#include <fstream>
using namespace std;

#define NMAX 100010

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N,M,X[NMAX];

void CautareBinara(int Val){
    int Left = 1, Right = N;
    int Sol = -1;
    while (Left <= Right) {
        int Mid = (Left + Right)/2;
        if (X[Mid] == Val) {
            Sol = Mid;
            Left = Mid + 1;
        }else if (X[Mid]<Val){
            Left = Mid+1;
        }else{
            Right = Mid - 1;
        }
    }
    g<<Sol<<"\n";
}
void CautareBinaraACeleiMaiMariPozitiiCuValoareMaiMicaSauEgalaDecatVal(int Val){
    int Left = 1, Right = N;
    int Sol = -1;
    while (Left <= Right) {
        int Mid = (Left + Right)/2;
        if (X[Mid] <= Val) {
            Sol = Mid;
            Left = Mid + 1;
        }else {
            Right = Mid-1;
        }
    }
    g<<Sol<<"\n";
}
void CautareBinaraACeleiMaiMicaPozitiiCuValoareMaiMareSauEgalaDecatVal(int Val){
    int Left = 1, Right = N;
    int Sol = -1;
    while (Left <= Right) {
        int Mid = (Left + Right)/2;
        if (X[Mid] >= Val) {
            Sol = Mid;
            Right = Mid - 1;
        }else {
            Left = Mid + 1;
        }
    }
    g<<Sol<<"\n";
}

void Read(){
    f>>N;
    for (int i = 1; i <= N; i++) {
        f>>X[i];
    }
    f>>M; int cod,x;
    for (int i = 1; i <= M; i++) {
        f>>cod>>x;
        if(cod == 0){
            CautareBinara(x);
        }else if(cod == 1){
            CautareBinaraACeleiMaiMariPozitiiCuValoareMaiMicaSauEgalaDecatVal(x);
        }else{
            CautareBinaraACeleiMaiMicaPozitiiCuValoareMaiMareSauEgalaDecatVal(x);
        }
    }
}

int main()
{
    Read();
    return 0;
}