#include <fstream>

using namespace std;

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

void last_poz(int x);
void lower_bound(int x);
void upper_bound(int x);

int n, m, tip, x, v[100005];

int main()
{
	int i;

	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	fin >> m;
	while (m--)
	{
		fin >> tip >> x;
		if (tip == 0)
			last_poz(x);
		else if (tip == 1)
			lower_bound(x);
		else upper_bound(x);
	}
	return 0;
}

void last_poz(int x)
{
	int in, sf, mij;

	in = 0; sf = n + 1;
	while (sf - in > 1)
	{
		mij = (in + sf) / 2;
		if (v[mij] <= x)
			in = mij;
		else sf = mij;
	}
	if (v[in] == x)
		fout << in << '\n';
	else fout << -1 << '\n';
}

void lower_bound(int x)
{
	int in, sf, mij;

	in = 0; sf = n + 1;
	while (sf - in > 1)
	{
		mij = (in + sf) / 2;
		if (v[mij] <= x)
			in = mij;
		else sf = mij;
	}
	fout << in << '\n';
}

void upper_bound(int x)
{
	int in, sf, mij;

	in = 0; sf = n + 1;
	while (sf - in > 1)
	{
		mij = (in + sf) / 2;
		if (v[mij] < x)
			in = mij;
		else sf = mij;
	}
	fout << sf << '\n';
}