#include <stdio.h>

int n, v[100005], m;

int caut0(int x)
{
	int p, u, m;
	p = 1; u = n;
	m = (p + u) / 2;
	while (p <= u)
	{
		if (v[m] == x && (v[m + 1] >= x || m + 1 > n)) return m;
		else if (v[m + 1] <= x) p = m + 1;
		else if (v[m + 1] > x) u = m - 1;
		m = (p + u) / 2;
	}
	return -1;
}

int caut1(int x)
{
	int p, u, m;
	p = 1; u = n; m = (p + u) / 2;
	while (p <= u)
	{
		if (v[m] <= x && (v[m + 1] > x || m + 1 > n)) return m;
		else if (v[m + 1] <= x) p = m + 1;
		else u = m - 1;
		m = (p + u) / 2;
	}
	return m;
}

int caut2(int x)
{
	int p, u, m;
	p = 1; u = n; m = (p + u) / 2;
	while (p <= u)
	{
		if (v[m] >= x && (v[m - 1] < x || m - 1 < 1)) return m;
		else if (v[m - 1] >= x) u = m - 1;
		else p = m + 1;
		m = (p + u) / 2;
	}
	return m;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	int i, op, x;
	scanf("%d",&n);
	for (i = 1; i <= n; i++) scanf("%d",v + i);
	scanf("%d",&m);
	for (i = 1; i <= m; i++)
	{
		scanf("%d %d",&op,&x);
		if (!op) printf("%d\n",caut0(x));
		else if (op == 1) printf("%d\n",caut1(x));
		else if (op == 2) printf("%d\n",caut2(x));
	}
	return 0;
}