#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
short type;
int bs0(int x, int left, int right)
{
	long mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		
			if (v[mid] <= x)
				left = mid + 1;
			else
				right = mid - 1;
	}
	mid = (left + right) / 2;
	if (v[mid] > x)
		mid--;
	if (v[mid] == x)
		return mid;
	else
		return -1;
	
}
int bs1(int x, int left, int right)
{
	long mid;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (v[mid] <= x)
			left = mid + 1;
		else
			right = mid;
	}
	mid = (left + right) / 2;
	if (v[mid] > x)
		mid--;
	return mid;
}
int bs2(int x, int left, int right)
{
	long mid;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (v[mid] < x)
			left = mid + 1;
		else
			right = mid;
	}
	mid = (right + left) / 2;
	if (v[mid] < x)
		mid++;
	return mid;

}
int main()
{
	int n, m;
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> v[i];
	fin >> m;
	for (int i = 0; i < m; i++)
	{
		int x;
		fin >> type >> x;
		if (type == 0)
		{
			fout << bs0(x, 1, n ) << '\n';
		}
		if (type == 1)
		{
			fout << bs1(x, 1, n ) << '\n';
		}
		if (type == 2)
		{
			fout << bs2(x, 1, n ) << '\n';
		}
	}
}