#include <fstream>
#include <iostream>
#define N 100010
std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");
int n, m, vect[N];
int bsearch0(int start, int final, int key)
{
	int mid;

	while (start <= final)
	{
		mid = (start + final) / 2;
		if (vect[mid] <= key)
			start = mid + 1;
		else
			final = mid - 1;
	}
	mid = (start + final) / 2;
	if (vect[mid + 1] == key) mid++;
	if (vect[mid] == key) return mid;
	return -2;
}
int bsearch1(int start, int final, int key)
{
	int mid;

	while (start <= final)
	{
		mid = (start + final) / 2;
		if (vect[mid] <= key)
			start = mid + 1;
		else
			final = mid - 1;
	}
	mid = (start + final) / 2;
	if (vect[mid] > key)
		mid--;
	return mid;
}
int bsearch2(int start, int final, int key)
{
	int mid;

	while (start < final)
	{
		mid = (start + final) / 2;
		if (vect[mid] < key)
			start = mid + 1;
		else
			final = mid - 1;
	}
	mid = (start + final) / 2;
	if (vect[mid] < key) return mid++;
	return mid;
}
int main()
{

	f >> n;
	for (int i = 0; i < n; i++)
		f >> vect[i];
	f >> m;
	while (m--)
	{
		int tip, x;
		f >> tip;
		f >> x;
		if (tip == 0)
		{
			g << bsearch0(0, n - 1, x) + 1 << '\n';
		}
		if (tip == 1) {
			g << bsearch1(0, n - 1, x) + 1 << '\n';
		}
		if (tip == 2) {
			g << bsearch2(0, n - 1, x) + 1 << '\n';
		}

	}
}