#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 (v[dr] == nr || v[st] == nr)
			{fprintf(out, "%d\n", dr);return;}


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

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

		if (type == 2)
		{
			if (nr <= v[1])
 				fprintf(out, "1\n");
			else
				if (st == n)
					fprintf(out, "%d\n", n);
					else
				if (v[dr] >= nr)
					fprintf(out, "%d\n", dr - 1);
				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;
}
/*
8
-1
8
-1
6
-1
5
-1
7
-1
-1
10
-1
5
6
9
14
-1
14
-1
1
14
5
-1
10
15
-1
-1
4
15
13
7
9
3
1
6
1

*/