#include <cstdio>
#define DIM 100005

FILE *out = fopen("cautbin.out", "w");
long long v[DIM], nr;
int n, m, type;

void search0(int st, int dr)
{
	if (st > dr)
	{
		fprintf(out, "-1\n");
		return;
	}

	int mij = st + (dr - st) / 2;
	if (v[mij] == nr)
	{
		fprintf(out, "%d\n", mij);
		return;
	}

	if (nr < v[mij])
		search0(st, mij - 1);

	else
		search0(mij + 1, dr);

}


void search1(int st, int dr)
{
	if (st == dr - 1)
	{
		if (v[st] != nr)
			fprintf(out, "%d\n", dr - 1);
		else
			fprintf(out, "%d\n", dr );
		return;
	}

	int mij = st + (dr - st) / 2;
	if (v[mij] == nr)
	{
		fprintf(out, "%d\n", mij);
		return;
	}

	if (nr < v[mij])
		search1(st, mij );

	else
		search1(mij , dr);
}

void search2(int st, int dr)
{
	if (st == dr - 1)
	{
		fprintf(out, "%d\n", dr);
		return;
	}

	int mij = st + (dr - st) / 2;
	if (v[mij] >= nr)
		search2(st, mij);

	else
		search2(mij, dr);

}

int main()
{
	FILE *f = fopen("cautbin.in", "r");
	fscanf(f, "%d", &n);
	int i;
	for (i = 1; i <= n; i++)
		fscanf(f, "%lld", &v[i]);

	fscanf(f, "%d", &m);

	for (i = 1; i <= m; i++)
	{
		fscanf(f, "%d%lld", &type, &nr);
		if (type == 0)
			search0(1, n);

		if (type == 1)
			search1(1, n);

		if (type == 2)
			search2(1, n);
	}

	fclose(f);
	fclose(out);
	return 0;
}