#include<fstream>
using namespace std;
int v[1000000];
int cautare_binara0(int st, int dr, int x)
{
	int mij;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (x >= v[mij]) st = mij + 1;
		else dr = mij - 1;
	}
	m = (st + dr) / 2;
	if (v[m] > x) m--;
	if (v[m] == x)return m;
	 return -1;
}
int cautare_binara1(int st, int dr, int x)
{
	int mij;
	while (st < dr)
	{
		mij = (st + dr) / 2;
		if (x >= v[mij]) st = mij + 1;
		else dr = mij;
	}
	m = (st + dr) / 2;
	if (v[m]>x)m--;
	return m;

}
int cautare_binara2(int st, int dr, int x)
{
	int mij;
	while (st <dr)
	{
		mij = (st + dr) / 2;
		if (x > v[mij]) st = mij + 1;
		else dr = mij;
	}
	m = (st + dr) / 2;
	if (v[m] < x)m++;
	return m;
}
int main()
{
	fstream g("cautbin.out", ios::out);
	fstream f("cautbin.in", ios::in);
	int n, i, m, k, x;
	f >> n;
	for (i = 1; i <= n; i++)
		f >> v[i];
	f >> m;
	for (i = 1; i <= m; i++)
	{
		f >> k >> x;
		if (k == 0)g << cautare_binara0(1, n, x) << endl;
		if (k == 1)g << cautare_binara1(1, n, x) << endl;
		if (k == 2)g << cautare_binara2(1, n, x) << endl;
	}
	f.close();
	g.close();
	return 0;
}