#include <stdio.h>

int poz1, poz2;

int caut0(int *v, int n, int x)
{
	if (x == v[n-1]) return n;
	else if (x > v[n-1]) return -1;
	else if (x < v[0]) return -1;
	
	int i=0, p=1;
	while (p < n) p <<= 1;
	while (p)
	{
		if (i+p < n && v[i+p] <= x)
			i += p;
		p >>= 1;
	}
	return i+1;
}

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;
		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;
		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: fprintf(out, "%d\n", caut0(v, n, x)); break;
			case 1: caut1(v, 0, n-1, x); fprintf(out, "%d\n", poz1+1); break;
			case 2: caut2(v, 0, n-1, x); fprintf(out, "%d", poz2+1); break;
		}
	}
	fclose(in); fclose(out);
	return 0;
}