# include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 
 # define dim 100005
 
 using namespace std;
 
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
 
 int a[ dim ];
 int n, k;
 int sol;
 
 void cauta1( int x )
 {
	 int mid, st, dr;
	 st = 1, dr = n;
	 
	 while ( st <= dr )
	 {
		 mid = ( st + dr ) / 2;
		 
		 if ( a[ mid ] <= x )
			 st = mid + 1;
		 else
			 dr = mid - 1;
	 }
	 
	 mid = ( st + dr ) / 2;
	 
	 if ( a[ mid ] > x )
		 mid--;
	 if ( a[ mid ] == x )
		 sol = mid;
	 else
		 sol = -1;
 }
 
 void cauta2( int x )
 {
	 int mid, st, dr;
	 st = 1;
	 dr = n;
	 
	 while ( st <= dr )
	 {
		 mid = ( st + dr ) / 2;
		 
		 if ( a[ mid ] <=x )
			 st = mid + 1;
		 else
			 dr = mid - 1;
	 }
	 
	 mid = ( st + dr ) / 2;
	 
	 if ( a[ mid ] > x )
		 sol = mid - 1;
	 else
		 sol = mid;
 }
 
  void cauta3( int x )
 {
	 int mid, st, dr;
	 st = 1;
	 dr = n;
	 
	 while ( st <= dr )
	 {
		 mid = ( st + dr ) / 2;
		 
		 if ( a[ mid ] < x )
			 st = mid + 1;
		 else
			 dr = mid - 1;
	 }
	 
	 mid = ( st + dr ) / 2;
	 
	 if ( a[ mid ] < x )
		 sol = mid + 1;
	 else
		 sol = mid;
 }
 
 
 void citire()
 {
	 int x, nr, i;
	 
	 f >> n;
	 for ( i = 1 ; i <= n ; i++ )
		 f >> a[ i ];
	 
	 f >> k;
	 for ( i = 1 ; i <= k ; i++ )
	 {
		 f >> nr >> x;
		 if ( nr == 0 )
		 {
			 cauta1( x );
			 g << sol << "\n";
		 }
		 else
		 if ( nr == 1 )
		 {
			 cauta2( x );
			 g << sol << "\n";
		 }
		 else
		 if ( nr == 2 )
		 {
			 cauta3( x );
			 g << sol << "\n";
		 }
	 }
	 
 }
 
 int main()
 {
	 citire();
	 return 0;
 }