#include <stdio.h>
#include <assert.h>

int N, M, v[100005];

inline int op0(int x)
{
	int st, dr, mid;

	for (st = 1, dr = N; st <= dr; )
	{
		mid = st + (dr-st) / 2;
		if (x < v[mid]) dr = mid-1;
		else if (v[mid] < x) st = mid+1;
		else return mid;
	}
	return -1;
}

inline int op1(int x)
{
	int st, dr, mid, last = 0;

	for (st = 1, dr = N; st <= dr; )
	{
		mid = st + (dr-st) / 2;
		if (v[mid] <= x) last = mid, st = mid+1;
		else dr = mid-1;
	}
	return last;
}

inline int op2(int x)
{
	int st, dr, mid, last = N+1;

	for (st = 1, dr = N; st <= dr; )
	{
		mid = st + (dr-st) / 2;
		if (x <= v[mid]) last = mid, dr = mid-1;
		else st = mid+1;
	}
	return last;
}

int main(void)
{
	int i, t, x;
	
	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", &M);
	for (; M; --M)
	{
		scanf("%d %d", &t, &x);
		if (!t)
			printf("%d\n", op0(x));
		else if (t == 1)
			printf("%d\n", op1(x));
		else
			printf("%d\n", op2(x));
	}
	return 0;
}