#include <fstream>

using namespace std;

#define INFILE "cautbin.in"
#define OUTFILE "cautbin.out"
#define VMAX 100002

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n, v[VMAX], queries;

void operatieTip0(int valoare){

    int st = 1, dr = n;

    while(st < dr){

        int mij = (st + dr + 1) / 2;

        if(v[mij] <= valoare){
            st = mij;
        }
        else{
            dr = mij - 1;
        }

    }

    if(v[dr] != valoare){
        fout << -1 << '\n';
        return;
    }

    fout << dr << '\n';

}

void operatieTip1(int valoare){

    int st = 1, dr = n;

    while(st < dr){

        int mij = (st + dr + 1) / 2;

        if(v[mij] <= valoare){
            st = mij;
        }
        else{
            dr = mij - 1;
        }

    }

    fout << dr << '\n';

}

void operatieTip2(int valoare){

    int st = 1, dr = n;

    while(st < dr){

        int mij = (st + dr) / 2;

        if(v[mij] < valoare){
            st = mij + 1;
        }
        else{
            dr = mij;
        }

    }

    fout << st << '\n';

}

void operatie(int tip, int valoare){

    // ! Tipul operatiei
    if(tip == 0){
        operatieTip0(valoare);
    }
    else if(tip == 1){
        operatieTip1(valoare);
    }
    else{
        operatieTip2(valoare);
    }

}

void afisare(){
    
    for(int i = 1; i <= n; ++i){
        fout << v[i] << " ";
    }

    fout << '\n';

}

void solve(){

    fin >> n;
    
    for(int i = 1; i <= n; ++i){

        fin >> v[i];

    }

    // afisare();

    int tip;
    int val;

    fin >> queries;

    // fout << queries << '\n';

    for(int i = 0; i < queries; ++i){

        fin >> tip >> val;

        operatie(tip, val);

    }

}

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