#include <fstream>

using namespace std;

int a[100100], x, t, n, op, i;

int cauta1(int x)
{
	int left = 1;
	int mid;
	int right = n;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (a[mid] > x)
			right = mid - 1;
		else if (a[mid] < x)
			left = mid + 1;
		else break;
	}
	if (a[mid] != x)
		return -1;
	else
	{
		while (a[mid] == x)
			mid++;
	}
	return mid;
}
int cauta2(int x)
{
	int left = 1;
	int mid;
	int right = n;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (a[mid] > x)
			right = mid - 1;
		else if (a[mid] < x)
			left = mid + 1;
		else break;
	}
	while (a[mid] <= x)
			mid++;
	return mid;
}
int cauta3(int x)
{
	int left = 1;
	int right = n;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (a[mid] > x)
			right = mid - 1;
		else if (a[mid] < x)
			left = mid + 1;
		else break;
	}
	while (a[mid] >= x)
			mid--;
	
	return mid;
}
int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f >> n;
	for (i = 1; i <= n; i++)
		f >> a[i];
	f >> t;
	for (i = 1; i <= t; i++)
	{
		f >> op >> x;
		if (op == 0)
		{
			g << cauta1(x) - 1 << "\n";
		}
		else if (op == 1)
		{
			g << cauta2(x) - 1<< "\n";
		}
		else if (op == 2)
		{
			g << cauta3(x) + 1<< "\n";
		}
	}
	return 0;
}