#include <fstream>
#include <cstdlib>
#define N_MAX 100011

using namespace std;
int v[N_MAX];
int main( void )
{
	int N, M, i, op, left, middle, right;
	ifstream in( "cautbin.in" );
	ofstream out( "cautbin.out" );
	in>>N;
	for( i=1; i <= N; ++i )
		in>>v[i];
	for( in>>M; M; --M )
	{
		in>>op>>i;
		left=1; right=N;
		if( 0 == op )
		{
			while( left <= right )
			{
				middle=(left+right)/2;
				if( v[middle] <= i )
					left=middle+1;
				else right=middle-1;
			}
			if( v[left-1] == i )
				out<<(left-1)<<'\n';
			else out<<"-1\n";
		}
		else if( 1 == op )
			 {
				 while( left <= right )
				 {
					 middle=(left+right)/2;
					 if( v[middle] <= i )
						 left=middle+1;
					 else right=middle-1;
				 }
				 out<<(left-1)<<'\n';
			 }
			 else if( 2 == op )
				  {
					  while( left <= right )
					  {
						  middle=(left+right)/2;
						  if( v[middle] >= i )
							  right=middle-1;
						  else left=middle+1;
					  }
					  out<<left<<'\n';
				  }
	}
	return EXIT_SUCCESS;
}