#include<fstream>

#define Nmax 100010

using namespace std;

int n, m, x, y, a[Nmax];

int search0 (int in, int sf, int key)
{
	int m;
	while (in <= sf)
	{
		m = (in + sf) / 2;
		if (a[m] <= key)
			in = m + 1;
		else
			sf = m - 1;
	}
	m = (in + sf) / 2;
	if (a[m] > key)
		--m;
	if (a[m] == key)
		return m;
	return -1;
}

int search1 (int in, int sf, int key)
{
	int m;
	while (in < sf)
	{
		m = (in +  sf) / 2;
		if (a[m] <= key)
			in = m + 1;
		else
			sf = m - 1;
	}
	m = (in + sf) / 2;
	if (a[m] > key)
		--m;
	return m;
}

int search2 (int in, int sf, int key)
{
	int m;
	while (in < sf)
	{
		m = (in + sf) / 2;
		if (a[m] < key)
			in = m + 1;
		else
			sf = m - 1;
	}
	m = (in + sf) / 2;
	if (a[m] < key)
		++m;
	return m;
}

int main()
{
	ifstream f("cautbin.in");
	ofstream h("cautbin.out");
	f >> n;
	for (int i = 1; i <= n; ++i)
		f >> a[i];
	f >> m;
	for (int i = 1; i <= m; ++i)
	{
		f >> x >> y;
		if (x == 0)
			h << search0 (1, n, y) << '\n';
		if (x == 1)
			h << search1 (1, n, y) << '\n';
		if (x == 2)
			h << search2 (1, n, y) << '\n';
	}
	f.close();
	h.close();
	return 0;
}