#include <fstream>
#include <vector>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, q, v[100005], x, sol;

int Cb0(int l, int r)
{
	if (l > r) return -1;
	int m = (l + r) / 2;
	if (v[m] > x) Cb0(l, m - 1);
	else if (v[m] < x) Cb0(m + 1, r);
	else
	{
		sol = m;
		Cb0(m + 1, r);
	}
	return sol;
}

int Cb1(int l, int r)
{
	if (l > r) return -1;
	int m = (l + r) / 2;
	if (v[m] > x) Cb1(l, m - 1);
	else if (v[m] <= x)
	{
		sol = m;
		Cb1(m + 1, r);
	}
	return sol;
}

int Cb2(int l, int r)
{
	if (l > r) return -1;
	int m = (l + r) / 2;
	if (v[m] >= x)
	{
		sol = m;
		Cb2(l, m - 1);
	}
	else
		Cb2(m + 1, r);
	return sol;
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> v[i];
	fin >> q;
	while (q--)
	{
		int type;
		fin >> type >> x;
		sol = -1;
		if (type == 0)
			fout << Cb0(1, n) << '\n';
		else if (type == 1)
			fout << Cb1(1, n) << '\n';
		else
			fout << Cb2(1, n) << '\n';
	}
	fin.close();
	fout.close();
	return 0;
}