#include <cstdio>
#include <cstdlib>
#include <cstring>

int bsearch(int *A,int l,int r,int key,bool exact) {
    
    int pos,stp;
    for(stp = 1; stp << 1 <= r - l + 1; stp <<= 1);
    
    for(pos = l; stp && pos <= r; stp >>= 1)
     if( A[pos + stp] <= key ) pos += stp; 
    
    if(exact) return A[pos] == key ? pos+1 : -1;
     else return A[pos] <= key ? pos+1 : -1;
}

int bsearch_rev(int *A,int l,int r,int key,bool exact) {
    
    int pos,stp;
    for(stp = 1; stp << 1 <= r - l + 1; stp <<= 1);
    
    for(pos = r; stp && pos >= l; stp >>= 1)
     if( A[pos - stp] >= key ) pos -= stp; 
    
    if(exact) return A[pos] == key ? pos+1 : -1;
     else return A[pos] >= key ? pos+1 : -1;
}

int main() {
    
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    
    int N,*A,M;
    scanf("%d",&N);
    
    A = (int*)calloc(N,sizeof(int));
    
    for(int i = 0; i < N; ++i) scanf("%d",&A[i]);
    
    scanf("%d",&M);
    for(int op,el; M-- ; ) {
    
               scanf("%d%d",&op,&el);
               
               switch(op) {
                          case 0: printf("%d\n",bsearch(A,0,N - 1,el,1)); break;
                          case 1: printf("%d\n",bsearch(A,0,N - 1,el,0)); break;
                          case 2: printf("%d\n",bsearch_rev(A,0,N - 1,el,0)); break;
               }
    }
    
    return 0;
}