#include <cstdio>
#define MAX 100001
int N, M, Val[MAX], op, X;

int BinarySearch0(int X)
{
	int Left = 1, Right = N, Mid;
	while (Right - Left > 1)
	{
		Mid = (Left + Right) / 2;
		if (Val[Mid] <= X) Left = Mid; else Right = Mid;
	}
	return Val[Right] == X ? Right : Val[Left] == X ? Left : -1;
}

int BinarySearch1(int X)
{
	int Left = 1, Right = N, Mid;
	while (Right - Left > 1)
	{
		Mid = (Left + Right) / 2;
		if (Val[Mid] <= X) Left = Mid; else Right = Mid;
	}
	return Val[Right] <= X ? Right : Val[Left] <= X ? Left : -1;
}

int BinarySearch2(int X)
{
	int Left = 1, Right = N, Mid;
	while (Right - Left > 1)
	{
		Mid = (Left + Right) / 2;
		if (Val[Mid] >= X) Right = Mid; else Left = Mid;
	}
	return Val[Left] >=	X ? Left : Val[Right] >= X ? Right : -1;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &Val[i]);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &op, &X);
		switch (op)
		{
		case 0: printf("%d\n", BinarySearch0(X)); break;
		case 1: printf("%d\n", BinarySearch1(X)); break;
		case 2: printf("%d\n", BinarySearch2(X)); break;
		}
	}
	return 0;
}