#include <fstream>
 
std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");

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

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

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

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

int main(){
    
    f >> n;
    
    for(int i = 1;i <= n;++i)
        f >> v[i];
    
    f >> t;
    
    while(t--){
        
        f >> type >> x;
        
        if(type == 0)
            g << query0(1,n,x) << '\n';
        else if(type == 1)
            g << query1(1,n,x) << '\n';
        else
            g << query2(1,n,x) << '\n';
    }
    
    return 0;
}