#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 lo, hi, mid;
 
    for (lo = li, hi = ls; lo <= hi; )
    {
        mid = (lo + hi) >> 1;

        if (what < vec[ mid ]) hi = mid - 1;

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

        else { while(vec[ mid + 1 ] == what) mid++; return mid; }
    }
    return -1;
}


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);
}