#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 = max(sol, m);
		Cb0(m + 1, r);
	}
}

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 = max(sol, m);
		Cb1(m + 1, r);
	}
}

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

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