#include <fstream>

int binKer(int k, int szam, int * tomb, int bal, int jobb){
    int kozep = (bal + jobb) / 2;
    if(bal >= jobb)
        return kozep;
    
        

    // szam == tomb[kozep]
    if(k == 0){
        if(tomb[kozep] > szam)
            return binKer(k, szam, tomb, bal, kozep);
        if(tomb[kozep] <= szam)
            return binKer(k, szam, tomb, kozep + 1, jobb);
        return -1;
    }
    // tomb[kozep] <= szam < tomb[kozep + 1] 
    if(k == 1){
        if(tomb[kozep] > szam)
            return binKer(k, szam, tomb, bal, kozep);
        if(tomb[kozep] <= szam)
            return binKer(k, szam, tomb, kozep + 1, jobb);
        return kozep;
    }
    // tomb[kozep - 1] < szam <= tomb[kozep]
    if(k == 2){
        if(tomb[kozep] >= szam)
            return binKer(k, szam, tomb, bal, kozep);
        if(tomb[kozep] < szam)
            return binKer(k, szam, tomb, kozep + 1, jobb);
        return kozep;
    }
    return -1;
}

int main(){
    std::ifstream bem("cautbin.in");
    std::ofstream kim("cautbin.out");
    int n, m;
    bem >> n;
    int * tomb = new int[n];
    for(int i = 0; i < n; i++)  bem >> tomb[i];
    bem >> m;
    
    for(int i = 0; i < m; i++){
        int k, szam;
        bem >> k >> szam;
        kim << binKer(k, szam, tomb, 0, n - 1) << ' ';
    }
}