#include <stdio.h>
#define FIN "cautbin.in"
#define FOUT "cautbin.out"
#define MAXN 100001

int n, 
    vec[ MAXN ],
    num_questions;

int request0(int li, int ls, int what) {

      int pos = -1, found = 0;
 
      int middle;
 
      while( li <= ls && !found )  {
 
          middle = (li + ls) >> 1;
 
          if( vec[ middle ] > what) {
 
               ls = middle - 1;
 
          } else if(vec[ middle ] < what) {
 
               li = middle + 1;
 
          } else {

                   found = 1;
        
                   while(vec[ middle + 1 ] == what) {
 
                         middle++;
                   }
 
                   pos = middle;  
                 }
       }
 
    return pos; 
};



int request1(int li, int ls, int what) {

    int lo, hi, mid, last = -1;

    for(lo = li, hi = ls; lo <= hi; ) {

        mid = (lo + hi) >> 1;

        if( vec[ mid ] <= what) last = mid, lo = mid + 1;

            else hi = mid - 1;  
    }  

    return last;
};

int request2(int li, int ls, int what) {

    int lo, hi, mid, last = -1;

    for(lo = li, hi = ls; lo <= hi; ) {

        mid = (lo + hi) >> 1;

        if( vec[ mid ] >= what) last = mid, hi = mid - 1;

            else lo = mid + 1;  
    }  

    return last;
};

void solve() {

     int i, 
         op, 
         j;

     freopen(FIN, "r", stdin);

     freopen(FOUT, "w", stdout);

     scanf("%d", &n);
 
     for(i = 1; i <= n; i++) scanf("%d", &vec[ i ]);

     scanf("%d", &num_questions);

     for(; num_questions; num_questions--) {

           scanf("%d %d", &op, &j);

           switch( op ) {

                   case 0: 
                   printf("%d\n", request0(1,n,j));   
                   break; 

                   case 1: 
                   printf("%d\n", request1(1,n,j));   
                   break;

                   case 2: 
                   printf("%d\n", request2(1,n,j));   
                   break; 
           }

     }
 
     fclose( stdin );

     fclose( stdout );
};

int main() {

    solve();
    
    return(0);
}