#include <iostream>
#include <fstream>

using namespace std;

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(){
	
	freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
	scanf("%d",&N);
	for( int i = 1 ; i <= N; i++ )
		scanf("%d", &a[i]);
	scanf("%d", &M);
	
	for( int i = 1; i <= M; i++ ){
		scanf("%d%d", &cod, &x );
		if( cod == 0 )
			printf("%d\n",binarySearch0( a, 1, N, x));
		else if( cod == 1 )
			printf("%d\n",binarySearch1( a, 1, N, x));
		else
			printf("%d\n",binarySearch2( a, 1, N, x));
	}
	
	return 0;
	
}