#include <stdio.h>

int caut0(int *v, int n, int x)
{
	if (x == v[n-1]) return n-1;
	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;
}

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

int caut2(int *v, int n, int x)
{
	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+2;
}

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