#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
int a[100001];

int Search1(int st, int dr, int x );
int Search2(int st, int dr, int x );
int Search3(int st, int dr, int x );

int main()
{
	fin >> n;
	for( int i = 0; i < n; ++i )
		fin >> a[i];
	fin >> m;
	int x, y;
	while( m )
	{
		fin >> x >> y;
		if( x == 0 )
			fout << Search1( 1, n, y ) << '\n';
		if( x == 1 )
			fout << Search2( 1, n, y ) << '\n';
		if( x == 2 )
			fout << Search3( 1, n, y ) << '\n';
		--m;
	}
	fin.close();
	fout.close();
	return 0;
}


int Search1(int st, int dr, int x )
{
	int mij;
	while( st <= dr )
	{
		mij = (st + dr) / 2;
		if( x > a[mij] )
			dr = mij - 1;
		else
			st = mij + 1;
	}
	mij = (st + dr) / 2;
	
	if( a[mij] > x )
		mij--;
	if( a[mij] == x )
		return mij + 1;
	return -1;
}
int Search2(int st, int dr, int x )
{
	int mij;
	while( st <= dr )
	{
		mij = (st + dr) / 2;
		if( x > a[mij] )
			dr = mij - 1;
		else
			st = mij + 1;
	}
	mij = (st + dr) / 2;
	
	if( a[mij] > x )
		mij--;
	return mij + 1;
}
int Search3(int st, int dr, int x )
{
	int mij;
	while( st <= dr )
	{
		mij = (st + dr) / 2;
		if( x >= a[mij] )
			dr = mij - 1;
		else
			st = mij + 1;
	}
	mij = (st + dr) / 2;
	
	if( a[mij] < x )
		mij++;
	return mij+1;
}