#include <stdio.h>

int poz0=-2, poz1, poz2;

void caut0(int *v, int stg, int dpt, int x)
{
	if (x < v[stg] || x > v[dpt])
	{
		if (poz0 == -2) poz0 = -1;
		return;
	}
	int m = stg + (dpt-stg)/2;
	if (v[m] == x)
	{
		poz0 = m+1;
		caut0(v, m+1, dpt, x);
	}
	else if (v[m] > x)
		caut0(v, stg, m, x);
	else
		caut0(v, m+1, dpt, x);
}

void caut1(int *v, int stg, int dpt, int x)
{
	if (stg == dpt) return;
	int m = stg + (dpt-stg)/2;
	if (v[m] <= x)
	{
		poz1 = m+1;
		caut1(v, m+1, dpt, x);
	}
	else
		caut1(v, stg, m, x);
}

void caut2(int *v, int stg, int dpt, int x)
{
	if (stg == dpt) return;
	int m = stg + (dpt-stg)/2;
	if (v[m] >= x)
	{
		poz2 = m+1;
		caut2(v, stg, m, x);
	}
	else
		caut2(v, m+1, dpt, x);
}

int main()
{
	int v[100000], n, m, i, c, x;
	FILE *in = fopen("cautbin.in", "r");
	FILE *out = fopen("cautbin.out", "w");
	fscanf(in, "%d", &n);
	for (i=0;i<n;i++) fscanf(in, "%d", &v[i]);
	fscanf(in, "%d", &m);
	for (i=0;i<m;i++)
	{
		fscanf(in, "%d%d", &c, &x);
		switch (c)
		{
			case 0: caut0(v, 0, n-1, x); fprintf(out, "%d\n", poz0); break;
			case 1: caut1(v, 0, n-1, x); fprintf(out, "%d\n", poz1); break;
			case 2: caut2(v, 0, n-1, x); fprintf(out, "%d", poz2); break;
		}
	}
	fclose(in); fclose(out);
	return 0;
}