#include <stdio.h>
#define nmax 100005

int ans, N, M, t, q;

int A[nmax];

void binary_search()
{
	ans = -1;

	int m, l, r;
	for (l = 1, r = N; l <= r; )
	{
		m = (l+r)/2;

		if (t == 0)
		{
			if (A[m] == q)
				ans = (l = m+1)-1;
			else if (A[m] > q)
				r = m-1;
			else
				l = m+1;
		}
		else if (t == 1)
		{
			if (A[m] <= q)
				ans = (l = m+1)-1;
			else
				r = m-1;
		}
		else
		{
			if (A[m] >= q)
				ans = (r = m-1)+1;
			else
				l = m+1;
		}
	}
}

int main()
{
	int i;

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

	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		scanf("%d", &A[i]);

	scanf("%d", &M);

	while (M--)
	{
		scanf("%d%d", &t, &q);
		binary_search();
		printf("%d\n", ans);
	}

	return 0;
}