#include<fstream>

using namespace std;

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

int v[100001], n;

int c0( int st, int dr, int x )
{
	int m = ( st + dr ) / 2;
	
	if( ( st == dr ) && ( v[st] != x ) )
		return -1;
	else
		if( v[m] == x )
		{
			while( v[m+1] == x && m < n )
				m++;
			
			return m;
		}
		else
			if( v[m] > x )
				return c0(st, m, x);
			else
				return c0(m+1, dr, x);
}

int c1( int st, int dr, int x )
{
	int m = ( st + dr ) / 2;
	
	if( v[n] < x )
		return n;
	
	if( st == dr && v[st] != x )
		return dr-1;
	else
		if( v[m] == x )
		{
			while( ( v[m+1] == x ) && ( m < n ) )
				m++;
				
			return m;
		}
		else
			if( v[m] > x )
				return c1 (st, m, x);
			else
				return c1 (m+1, dr, x);	
}

int c2( int st, int dr, int x )
{
	int m = ( st + dr ) / 2;
	
	if( v[1] > x )
		return 1;
	
	if( st == dr && v[st] != x )
		return st;
	else
		if( v[m] == x )
		{
			while( v[m-1] == x && m > 1 )
				m--;

			return m;
		}
		else
			if( v[m] > x )
				return c2 (st, m, x);
			else
				return c2 (m+1, dr, x);	
	
}


int main()
{
	int i, x, j, m;
	
	fin>>n;
	
	for( i = 1; i <= n; i++ )
		fin>>v[i];
	
	fin>>m;
	
	for( i = 1; i <= m; i++ )
	{
		fin>>j>>x;
		
		if( j == 0 )
			fout<<c0( 1, n, x)<<'\n'; 
		
		if( j == 1 )
			fout<<c1( 1, n, x)<<'\n';
			
		if( j == 2 )
			fout<<c2( 1, n, x)<<'\n'; 
	}
		
	return 0;
}