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

//vector <int> x;
long x[100001];

long a, code, n, m;

long cautbin1(long st, long dr)
{
	long mid;

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

	if (x[mid] == a)
		return mid;
	
	return -1;
}

long cautbin2(long st, long dr)
{
	long mid;

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

long cautbin3(long st, long dr)
{
	long mid;

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

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

	scanf("%ld", &n);
	for (long i = 1; i <= n; ++i)
	{
		scanf("%ld", &x[i]);
	}

	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(1, n));
		}
		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(1, n));
		}
		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(1, n));
		}
	}

	return 0;
}