#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001], n, i;
int CautBin2(int Valoare2) {
    int low, high, mid, rezultat;
    low = 1;
    high = n;
    while (low <= high) {
        mid = (low + high) / 2;
        if (v[mid] < Valoare2) {
            low = mid + 1;
        } else {
            high = mid-1;
            rezultat = mid;
        }
    }
    return rezultat;
}
int CautBin1(int Valoare1) {
    int low, high, mid, rezultat=0;
    low = 1;
    high = n;
    while (low <= high){
        mid = (low + high) / 2;
        if (v[mid] <= Valoare1) {
            low = mid + 1;
            rezultat = mid;
        } else {
            high = mid-1;
        }
    }
    return rezultat;
}
int main(){
    int TipIntrebare, NrIntrebari, NrDeVerificat, PozNrVerificat;
    fin >> n;
    for (i = 1; i<=n; i++)
        fin >> v[i];
    fin >> NrIntrebari;
    for (i = 1; i <= NrIntrebari; i++){
        fin >> TipIntrebare >> NrDeVerificat;
        if (TipIntrebare == 0){
            PozNrVerificat = CautBin1(NrDeVerificat);
            if (v[PozNrVerificat] == NrDeVerificat) {
                fout << PozNrVerificat << '\n';
            } else {
                fout << -1 << '\n';
            }
        } else if (TipIntrebare == 1){
            fout << CautBin1(NrDeVerificat) << '\n';
        } else if (TipIntrebare == 2){
            fout << CautBin2(NrDeVerificat) << '\n';
        }
    }
    return 0;
}