#include <cstdio>
using namespace std;
 
int arr[100000];
int n,m;
 
 
int opt0 (int x , int l , int r){
    int mid = (l+r)/2; 
    if (r < l){
        return -1;
    }
    if ( (x == arr[mid]) && ((x != arr[mid+1]) || (mid == r))){
        return mid+1;   
    }
    if ( x < arr[mid]){
            return opt0 (x,l,mid-1);        
    }
    if (arr[mid] <= x)
        return opt0 (x,mid+1,r);
}
 
int opt1 (int x , int l , int r){
    int mid = (l+r)/2; 
    if (r < l){
        return -1;
    }
    if ( (x >= arr[mid]) && ((x < arr[mid+1]) || (mid == r))){
        return mid+1;   
    }
    if ( x < arr[mid]){
            return opt1 (x,l,mid-1);        
    }
    if (arr[mid] <= x)
        return opt1 (x,mid+1,r);
}
 
int opt2 (int x , int l , int r){
    int mid = (l+r)/2; 
    if (r < l){
        return -1;
    }
    if ( (x <= arr[mid]) && ((x > arr[mid-1]) || (mid == r))){
        return mid+1;   
    }
    if ( x <= arr[mid]){
            return opt2 (x,l,mid-1);        
    }
    if (arr[mid] < x)
        return opt2 (x,mid+1,r);
}
 
int main (){
 
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
 
 
    scanf ("%d",&n);
 
    for (int i = 0; i < n; i++){
        scanf("%d",&arr[i]);    
    }
 
     
    int opt;
    int x;
 
    scanf("%d",&m);
  
    for (int i = 0; i < m;i++){
        int r = n-1;
        int l = 0;      
        scanf ("%d %d" ,&opt,&x);
        if (opt == 0){
            printf("%d \n",opt0(x,l,r));    
        }
        else if (opt == 1){
            printf("%d \n",opt1(x,l,r));
        }
        if (opt == 2)
            printf("%d \n",opt2(x,l,r));
         
 
    }
 
    fclose(stdin);
    fclose(stdout);     
}