#include <fstream>
#include <bits/stdc++.h>


using namespace std;


const int BUFFER_SIZE = 1 << 17; 
	
char buffer[BUFFER_SIZE];	
	
int pos = BUFFER_SIZE;
	

inline char next() {
    if (pos == BUFFER_SIZE) {
        fread(buffer, 1, BUFFER_SIZE, stdin);
        pos = 0;
    }
    return buffer[pos++];	
}

inline int read() {
    int x = 0, neg = 1;
    char c = next();
    if (c == '-') {
    	neg = -1;
    }
    while (!('0' <= c && c <= '9')) {
        c = next();
	
    }
    while ('0' <= c && c <= '9') {
        x = (x << 3) + (x << 1) + (c - '0');
        c = next();
    }		
    return x * neg;
}


void cautbin0(int *vect, int n, int y){
	int hi, lo, mid;
	hi = n+1;
	lo = 0;
	while ( hi - lo > 1){
		mid = ( hi + lo )/2;
			if( vect[mid] > y )
				hi = mid;
			else
				lo = mid;
	}
	if( vect[lo] != y  ||  hi == n  )
		printf("%d\n",-1);
	else
		printf("%d\n",lo);

}

void cautbin1(int *vect, int n, int y){
	int hi, lo, mid;
	hi = n+1;
	lo = 0;
	while ( hi - lo > 1){
		mid = ( hi + lo )/2;
			if( vect[mid] > y )
				hi = mid;
			else
				lo = mid;
	}
		printf("%d\n",lo);
}
void cautbin2(int *vect, int n, int y){
	int hi, lo, mid;
	hi = n;
	lo = -1;
	while ( hi - lo > 1){
		mid = ( hi + lo )/2;
			if( vect[mid] < y )
				lo = mid;
			else
				hi = mid;
	}
	  printf("%d\n",hi);

}




int main(){
freopen("cautbin.in", "r", stdin);
freopen("cautbin.out", "w", stdout);

 int *vect, n, cerinte, i, x, y;
  n = read();
 vect = new int[n+1];
 for( i = 1; i <= n; i++){
 	vect[i] = read();
 }
 cerinte = read();
 for( i = 1; i <= cerinte; i++){
 	x = read();
 	y = read();
 	if( x == 0 ) {
 		cautbin0(vect, n, y);
 	}
 	else if( x == 1 ){
 		cautbin1(vect, n, y);
 	}
 	else if( x == 2 ){
 		cautbin2(vect, n, y);
 	}

 }

}