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

int N, v[100005], M;

int BS(int x)
{
	int lo, hi, mid, last = 0;

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

int main(void)
{
	int i, t, x, poz;
	
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);	
	assert(1 <= N && N <= 100000);
	for (i = 1; i <= N; ++i)
		scanf("%d", &v[i]);
	
	scanf("%d", &M);
	assert(1 <= M && M <= 100000);
	for (; M; --M)
	{
		scanf("%d %d", &t, &x);
		if (!t)
		{
			poz = BS(x);
			if (!poz || v[poz] < x)
				printf("-1\n");
			else
				printf("%d\n", poz);
			continue;
		}
		if (t == 1)
		{
			printf("%d\n", BS(x));
			continue;
		}
		poz = BS(x);
		if (v[poz] < x) ++poz;
		printf("%d\n", poz);
	}
}