#include <cstdio>
#include <vector>
using namespace std;

vector <int> x;

long a, code, n, m;

long cautbin1(long st, long dr)
{
	if (dr - st == 0)
	{
		if (x[dr] == a)
			return dr + 1;
		else
			return dr;
	}

	long mid = (st + dr) / 2;

	if (x[mid] <= a)
		return cautbin1(mid + 1, dr);
	else
		return cautbin1(st, mid - 1);
}

long cautbin2(long st, long dr)
{
	if (dr - st == 0)
	{
		if (x[dr] <= a)
			return dr + 1;
		else
			return dr;
	}

	long mid = (st + dr) / 2;

	if (x[mid] <= a)
		return cautbin1(mid + 1, dr);
	else
		return cautbin1(st, mid - 1);
}

long cautbin3(long st, long dr)
{
	if (dr - st == 0)
	{
		if (x[dr] >= a)
			return dr + 1;
		else
			return dr;
	}

	long mid = (st + dr) / 2;

	if (x[mid] < a)
		return cautbin1(mid + 1, dr);
	else
		return cautbin1(st, mid - 1);
}

int main()
{
	freopen ("cautbin.in", "rt", stdin);
	freopen ("cautbin.out", "wt", stdout);

	scanf("%ld", &n);
	for (long i = 0; i < n; ++i)
	{
		scanf("%ld", &a);
		x.push_back(a);
	}

	scanf("%ld", &m);
	for (long i = 0; i < m; ++i)
	{
		scanf("%ld %ld", &code, &a);
		if (code == 0)
		{
			//cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
			printf("%ld\n", cautbin1(0, n - 1));
		}
		else
		if (code == 1)
		{
			//cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir
			printf("%ld\n", cautbin2(0, n - 1));
		}
		else
		{
			//cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir
			printf("%ld\n", cautbin3(0, n - 1));
		}
	}

	return 0;
}