#include <fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
const int N = 1e5;
int n , v[N + 1] , m;
int solve_0(int low , int hi , int value , int rez){
    if(low > hi){
        return rez;
    }
    int mid = (low + hi) / 2;
    if(v[mid] == value){
        return solve_0(mid + 1 , hi , value , mid);
    }
    else if(v[mid] < value){
        return solve_0(mid + 1 , hi , value , rez);
    }
    else{
        return solve_0(low , mid - 1 , value , rez);
    }
}
int solve_1(int low , int hi , int value , int rez){
    if(low > hi){
        return rez;
    }
    int mid = (low + hi) / 2;
    if(v[mid] > value){
        return solve_1(low , mid - 1 , value , rez);
    }
    if(v[mid] <= value){
        return solve_1(mid + 1 , hi , value , mid);
    }
}
int solve_2(int low , int hi , int value , int rez){
    if(low > hi){
        return rez;
    }
    int mid = (low + hi) / 2;
    if(v[mid] < value){
        return solve_2(mid + 1 , hi , value , rez);
    }
    if(v[mid] >= value){
        return solve_2(low , mid - 1 , value , mid);
    }
}

int main(){
    in >> n;
    for(int i = 1 ; i <= n ; i++){
        in >> v[i];
    }
    in >> m;
    while(m--){
        int q , nr;
        in >> q >> nr;
        int rez = 0;
        if(q == 0){
            out << solve_0(1 , n , nr , -1) << '\n';
        }
        else if(q == 1){
            out << solve_1(1 , n , nr , rez) << '\n';
        }
        else{
            out << solve_2(1 , n , nr , rez) << '\n';
        }
    }
}