#include <cstdio>

const int MAX_N = 100002;
const char infile[] = "cautbin.in";
const char outfile[] = "cautbin.out";

int a[ MAX_N ];
int N, M, op, val;

int search0( int left, int right, int val ){
	int div;
	while( left <= right ){
		div = ( left + right ) / 2;
		if( a[ div ] <= val )
			left = div + 1;
		else
			right = div - 1;
	}

	div = ( left + right ) / 2;
	if( a[ div ] > val )
		div--;
	if( a[ div ] == val )
		return div;
	return -1;
}

int search1( int left, int right, int val ){
	int div;
	while( left < right ){
		div = ( left + right ) / 2;
		if( a[ div ] <= val )
			left = div + 1;
		else
			right = div;
	}

	div = ( left + right ) / 2;
	if( a[ div ] > val )
		div--;
	return div;
}


int search2( int left, int right, int val ){
	int div;
	while( left < right ){
		div = ( left + right ) / 2;
		if( a[ div ] < val )
			left = div + 1;
		else
			right = div;
	}

	div = ( left + right ) / 2;
	if( a[ div ] < val )
		div++;
	return div;
}

int main(){
	FILE *f, *g;
	f = fopen( infile, "rt" );
	g = fopen( outfile, "wt" );

	fscanf( f, "%d", &N );
	for( int i = 1; i <= N; ++i )
		fscanf( f, "%d", &a[ i ] );
	fscanf( f, "%d", &M );
	
	for(; M; M-- ){
		fscanf( f, "%d %d", &op, &val );
		if( op == 0 )
			fprintf( g, "%d\n", search0( 1, N, val ) );
		if( op == 1 )
			fprintf( g, "%d\n", search1( 1, N, val ) );
		if( op == 2 )
			fprintf( g, "%d\n", search2( 1, N, val ) );
	}
	return 0;
}