#include <iostream>
#include <fstream>

std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");

const int NMAX = 100'005;
int n,v[NMAX],q,t,x;

inline int cautare_binara(int left,int right,int value){
    
    int sol = -1;
    
    while(left <= right){
        
        int mid = (left + right) / 2;
        
        if(v[mid] == value){
            sol = mid;
            left = mid + 1;
            continue;
        }
        
        if(v[mid] < value)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return sol;
}

inline int cautare_binara1(int left,int right,int value){
    
    int sol = -1;
    
    while(left <= right){
        
        int mid = (left + right) / 2;
        
        if(v[mid] <= value){
            sol = mid;
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    
    return sol;
}

inline int cautare_binara2(int left,int right,int value){
    
    int sol = -1;
    
    while(left <= right){
        
        int mid = (left + right) / 2;
        
        if(v[mid] >= value){
            sol = mid;
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    
    return sol;
}

int main(){
    
    f >> n;
    
    for(int i = 1;i <= n;++i)
        f >> v[i];
    
    f >> q;
    
    while(q--){
        
        f >> t >> x;
        
        if(t == 0)
            g << cautare_binara(1,n,x) << '\n';
        else if(t == 1)
            g << cautare_binara1(1,n,x) << '\n';
        else
            g << cautare_binara2(1,n,x) << '\n';
    }
    
    return 0;
}