#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;
	}
	mij = (st + dr) / 2;
	if (v[mij] > x) mij--;
	if (v[mij] == x)return mij;
	 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;
	}
	mij = (st + dr) / 2;
	if (v[mij]>x)mij--;
	return mij;

}
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;
	}
	mij = (st + dr) / 2;
	if (v[mij] < x)mij++;
	return mij;
}
int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	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;
}