#include <iostream>
#include <fstream>

using namespace std;

static string Output_File_Name = "cautbin.out";
static string Input_File_Name = "cautbin.in";

ofstream outFile;
ifstream inFile;

int N,M,*A;

int bsearch0(int val,int step);

int bsearch1(int val,int step);

int bsearch2(int val,int step);

int main() {

    inFile.open("cautbin.in");
    outFile.open("cautbin.out");
    int q,val;
    inFile >> N;
    A = new int[N];
    int step;
    for (step = 1; step < N; step <<= 1);
    for(int i = 0; i < N ; i++){
        inFile >> A[i];
    }
    inFile >> M;

    for (int i = 0;i < M ; i++){
        inFile >> q >> val;
        switch(q){
            case 0 : outFile << bsearch0(val,step) << endl;break;
            case 1 : outFile << bsearch1(val,step) << endl;break;
            case 2 : outFile << bsearch2(val,step) << endl;break;
        }
    }

    inFile.close();
    outFile.close();

    return 0;
}

int bsearch0(int val,int step){
    int 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)
        return i + 1;
    else return -1;
}

int bsearch1(int val,int step){
    int i;
    //for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] <= val)
            i += step;

    return  i + 1;
}

int bsearch2(int val,int step){
    int i;
    //for (step = 1; step < N; step <<= 1);
    for (i = N - 1; step; step >>= 1)
        if (i  - step > 0 && A[i - step] >= val)
            i -= step;

    return  i + 1;
}