#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];

int caut0(int p, int u, int k)
{
	int mij;
	while (p <= u)
	{
		mij = (p + u) / 2;
		if (v[mij]<k)
			p = mij + 1;
		else
			u = mij - 1;
	}
	mij = (p + u) / 2;
	if (v[mij]>k)
		mij--;
	if (v[mij] == k)
		return mij;

	return -1;
}

int caut1(int p, int u, int k)
{
	int mij, n = u;
	while (p<u)
	{
		mij = (p + u) / 2;
		if (v[mij] <= k)
			p = mij + 1;
		else
			u = mij;
	}
	mij = (p + u) / 2;
	if (v[mij]>k)
		mij--;

	return mij;
}

int caut2(int p, int u, int k)
{
	int mij;
	while (p<u)
	{
		mij = (p + u) / 2;
		if (v[mij]<k)
			p = mij + 1;
		else
			u = mij;
	}
	mij = (p + u) / 2;
	if (v[mij]<k)
		mij++;

	return mij;
}

int main()
{
	int i, n, mij, mod, x=0;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i<=n; i++)
		scanf("%d", &v[i]);

	scanf("%d", &mij);

	while (mij--)
	{
		scanf("%d%d", &mod, &x);
		if (mod == 0)
			printf("%d\n", caut0(1, n, x));
		if (mod == 1)
			printf("%d\n", caut1(1, n, x));
		if (mod == 2)
			printf("%d\n", caut2(1, n, x));
	}
	return 0;
}