#include <fstream>
#include <iostream>
#define N 100010

std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");
int n, m, v[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 bsearch0(int p, int u, int key) {
	int m;

	while (p <= u) {
		m = (p + u) / 2;
		if (v[m] <= key)
			p = m + 1;
		else
			u = m - 1;
	}
	m = (p + u) / 2;

	if (v[m] > key) m--;
	if (v[m] == key)
		return m + 1;
	return -1;
}

int bsearch1(int p, int u, int key) {
	int m, n = u;

	while (p < u) {
		m = (p + u) / 2;
		if (v[m] <= key)
			p = m + 1;
		else
			u = m;
	}

	m = (p + u) / 2;
	if (v[m] > key)
		--m;
	return m + 1;
}

int bsearch2(int p, int u, int key) {
	int m;

	while (p < u) {
		m = (p + u) / 2;
		if (v[m] < key)
			p = m + 1;
		else
			u = m;
	}

	m = (p + u) / 2;
	if (v[m] < key)
		++m;
	return m + 1;
}
int main()
{

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

	}
}