#include <cstdio>
#define DIM 100005
int n, v[DIM], type, m, nr;
FILE *out = fopen("cautbin.out", "w");

void divide(int st, int dr)
{

	if (st >= dr)
	{
		if (type == 0)
			if (v[st] == nr)
				fprintf(out, "%d\n", st);
			else
				fprintf(out, "-1\n");

		if (type == 1)
			fprintf(out, "%d\n", dr);

		if (type == 2)
			if (nr <= v[dr] || dr == n )
				fprintf(out, "%d\n", dr );
			else

				fprintf(out, "%d\n", dr + 1);
	}

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

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

		else
			divide(mij + 1, dr);
	}

}

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

	fscanf(f, "%d", &m);
	for (i = 1; i <= m; i++)
	{
		fscanf(f, "%d%d", &type, &nr);
		divide(1, n);
	}
	fclose(f);
	fclose(out);
	return 0;
}