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

int N, M;
long long v[100005];

int BS1(int x)
{
	int lo, hi, mid;

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

int BS2(int x)
{
	int lo, hi, mid, last = -10000;

	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 BS3(int x)
{
	int lo, hi, mid, last = -10000;

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

int main(void)
{
	int i, t, x;
	
	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("%lld", &v[i]);
		assert(1 <= v[i] && v[i] <= ((long long)1<<31));
	}
	for (i = 1; i < N; ++i)
		assert(v[i] <= v[i+1]);
	
	scanf("%d", &M);
	assert(1 <= M && M <= 100000);
	for (; M; --M)
	{
		scanf("%d %d", &t, &x);
		if (!t)
			printf("%d\n", BS1(x));
		else if (t == 1)
			printf("%d\n", BS2(x));
		else
			printf("%d\n", BS3(x));
	}
}