#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int  binarySearch( vector<int> &v, int low, int high, int key ){
	if( low > high ){
		return -1;
	}
	int mid = ( low + high ) / 2;
	if( v[ mid ] == key )
		return mid;
	if( v[ mid ] < key )
		return binarySearch( v, mid + 1, high, key );
	else
		return binarySearch( v, low, mid - 1 , key ); 
}

int main(){
	ifstream in ( "cautbin.in" );
	ofstream out ( "cautbin.out" );
	int size, nrQ;
	vector<int> v;
	in >> size;
	for( int i = 0; i < size; i++ ){
		int tmp;
		in >> tmp;
		v.push_back( tmp );
	}
	in >> nrQ;
	for( int i = 0; i < nrQ; i++ ){
		int q, key;
		in >> q >> key;
		int index = binarySearch( v, 0, v.size() - 1, key );
		if( q == 0 ){
			if( index == -1 ) out << -1 << "\n";
			else{
				while( v[ index ] == v[ index + 1 ] )
					index++;
				out << index + 1 << "\n";	
			}
		}
		if( q == 1 ){
			if( index == -1 ){
				int i = 0;
				while( v[ i ] <= key ){
					i++;
				}
				out << i << "\n";
			}
			else{
				while( v[ index ] == v[ index + 1 ] )
					index++;
				out << index + 1 << "\n";
			}
		}
		if( q == 2 ){
			if( index == -1 ){
				int i = v.size() - 1;
				while( v[ i ] >= key )
					i--;
				out << i + 2 << "\n";	
			}
			else{
				while( v[ index ] == v[ index - 1 ] ){
					index--;
				}
				out << index + 1 << "\n";
			}
		}
	}
	in.close();
	out.close();
	return 0;
}