#include <iostream>
#include <fstream>

using namespace std;

ifstream in("cautbin.in"); 
ofstream out("cautbin.out");
int N,M,cod,x, a[100005];

int binarySearch0(int* a, int left, int right, int x ){

	int mid;

	while( left <= right ){
		mid = (left+right)/2;
		if( a[mid] <= x )
			left = mid+1;
		else
			right = mid-1;
	}
	

	if( a[left-1] == x ) return left-1;
	return -1;
	
}

int binarySearch1( int*a, int left, int right, int x ){

	int mid;
	
	while( left <= right ){
	
		mid = (left+right)/2;
		
		if( a[mid] <= x )
			left = mid+1;
		else
			right = mid-1;
	}
	
		return left-1;
}

int binarySearch2(int*a, int left, int right, int x ){

	int mid;
	
	while( left <= right ){
		mid = (left+right)/2;
		
		if( a[mid] >= x )
			right = mid-1;
		else
			left =  mid+1;
	}
	
		return right + 1;
}
int main(){
	
	in >> N;
	for( int i = 1 ; i <= N; i++ )
		in >> a[i];
	in >> M;
	for( int i = 0; i < M; i++ ){
		in >> cod >> x;
		if( cod == 0 )
			out<< binarySearch0( a, 1, N, x)<<endl;
		else if( cod == 1 )
			out<< binarySearch1( a, 1, N, x)<<endl;
		else
			out<< binarySearch2( a, 1, N, x)<<endl;
	}
	
	return 0;
	
}