#include<fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, i, t, x, v[100005], m;

int cautbinar0(int st, int dr, int x)
{
	int m;
	while (st <= dr)
	{
		m = (st + dr) / 2;
		if (v[m] <= x) st = m + 1;
		else dr = m - 1;
	}
	m = (st + dr) / 2;
	if (v[m]>x) m--;
	if (v[m] == x) return m;
	return -1;
}

int cautbinar1(int st, int dr, int x)
{
	int m;
	while (st<dr)
	{
		m = (st + dr) / 2;
		if (v[m] <= x) st = m + 1;
		else    dr = m;
	}
	m = (st + dr) / 2;
	if (v[m]>x)  --m;
	return m;
}

int cautbinar2(int st, int dr, int x)
{
	int m;
	while (st<dr)
	{
		m = (st + dr) / 2;
		if (v[m]<x)  st = m + 1;
		else    dr = m;
	}
	m = (st + dr) / 2;
	if (v[m]<x)  ++m;
	return m;
}

int main()
{
	f >> n;
	for (i = 1; i <= n; i++)
		f >> v[i];
	f >> m;
	for (i = 1; i <= m; i++)
	{
		f >> t >> x;
		if (t == 0)   g << cautbinar0(1, n, x) << "\n";
		if (t == 1)   g << cautbinar1(1, n, x) << "\n";
		if (t == 2)   g << cautbinar2(1, n, x) << "\n";
	}
	f.close();
	g.close();
	return 0;
}