#include <fstream>
#include <algorithm>

using namespace std;

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

int A[100005], n, m;

int binary_search0(int st, int dr, int target)
{
	int mid;
	while( st <= dr){
		mid = st + (dr-st)/2;
		if( A[mid] <= target ) st = mid + 1;
		else dr = mid - 1;
	}

	if( A[mid] == target ) return mid;
	mid--;
	if( A[mid] == target ) return mid;
	return -1;
}

int binary_search1(int st, int dr, int target)
{
	
	int mid;
	while( st <= dr){
		mid = st + (dr-st)/2;
		if( A[mid] <= target ) st = mid + 1;
		else dr = mid - 1;
	}

	if( A[mid] <= target ) return mid;
	mid--;
	if( A[mid] <= target ) return mid;
	return -1;
}

int binary_search2(int st, int dr, int target)
{
	int mid;
	while( st <= dr){
		mid = st + (dr - st)/2;
		if( A[mid] >= target ) dr = mid - 1;
		else st = mid + 1;
	}

	if( A[mid-1] >= target ) return mid - 1;
	return mid;
}



int main()
{
	inFile >> n;

	for(int i = 1; i <= n; i++){
		inFile >> A[i];
	}

	inFile >> m;

	int op, x;
	while(m--){
		inFile >> op >> x;

		if( op == 0 ) outFile << binary_search0(1, n, x) << "\n";
		if( op == 1 ) outFile << binary_search1(1, n, x) << "\n";
		if( op == 2 ) outFile << binary_search2(1, n, x) << "\n";
		//if( op == 2 ) outFile << lower_bound(A+1, A+n+1, x) - A << "\n";
	}

	
}