#include <iostream>
#include <fstream>

using namespace std;

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

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] > x ) left--;
	if( a[left] == x)
		return left;
	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;
	}
	
	if( a[left] > x )
		return left-1;
	
	return left;
}

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;
	}
	
	if (a[right] < x )
		return right + 1;
	else
		return right;
}
int main(){
	
	int N,M, *a;
	in >> N;
	a = new int[N];
	for( int i = 0 ; i < N; i++ )
		in >> a[i];
	in >> M;
	int cod,x;
	for( int i = 0; i < M; i++ ){
		in >> cod >> x;
		if( cod == 0 )
			out<< binarySearch0( a, 0, N-1, x)+1<<endl;
		else if( cod == 1 )
			out<< binarySearch1( a, 0, N-1, x)+1<<endl;
		else
			out<< binarySearch2( a, 0, N-1, x)+1<<endl;
	}
	
	return 0;
	
}