#include <stdio.h>
#define NMax 100005

int n, v[NMax];

int cbin0(int val)
{
	if (v[n-1] == val)
		return val;

	int lo = 0, hi = n-1, mi;

	while (hi - lo > 1)
	{
		mi = lo + (hi - lo) / 2;
		if (v[mi] > val)
			hi = mi;
		else
			lo = mi;
	}

	if (v[hi] == val)
		return hi;
	if (v[lo] == val)
		return lo;
	return -2;
}

int cbin1(int val)
{
	int lo = 0, hi = n-1, mi;

	while (hi - lo > 1)
	{
		mi = lo + (hi - lo) / 2;
		if (v[mi] > val)
			hi = mi;
		else
			lo = mi;
	}

	if (v[hi] <= val)
		return hi;
	return lo;
}
int cbin2(int val)
{
	int lo = 0, hi = n-1, mi;

	while (hi - lo > 1)
	{
		mi = lo + (hi - lo) / 2;
		if (v[mi] < val)
			lo = mi;
		else
			hi = mi;
	}

	if (v[lo] >= val)
		return lo;
	return hi;
}

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &v[i]);

	int t;
	scanf("%d", &t);

	while (t--)
	{
		int op, val;
		scanf("%d %d", &op, &val);

		if (val == 5)
			val = 5;

		if (op == 0)
			printf("%d\n", cbin0(val) + 1);
		if (op == 1)
			printf("%d\n", cbin1(val) + 1);
		if (op == 2)
			printf("%d\n", cbin2(val) + 1);
	}	

	return 0;
}