#include <fstream>


using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");


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+1  )
		g << -1<<"\n";
	else
		g << lo<<"\n";

}

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;
	}
		g << lo<<"\n";

}
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;
	}
		g<< hi<<"\n";

}




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

 }

}