#include <bits/stdc++.h>
using namespace std;

ifstream in ("cautbin.in");
ofstream out ("cautbin.out");

int v[100001], i, j;

int caz0 (int k)
{
	int st = 0, dr = n-1;
	int val = -1;
	while (st <= dr)
	{
		int mid = (st + dr) / 2;
		if (v[mid] == k)
		{
			val = mid; // memoram pozitia
			st = mid + 1; // caut mai departe in dreapta
		}
		else
		{
			if (v[mid] < k)
				st = mid + 1;
			else
				dr = mid - 1;
		}
	}
	return val;
}

int caz1 (int k)
{
	int st = 0, dr = n-1;
	int val = -1;

	while (st <= dr)
	{
		int mid = (st + dr) / 2;
		if (v[mid] <= k)
		{
			val = mid;
			st = mid + 1; // caut mai departe in dreapta
		}
		else
		{
			dr = mid - 1;
		}
	}
	return val;
}

int caz2 (int k)
{
	int st = 0, dr = n-1;
	int val = -1;

	while (st <= dr)
	{
		int mid = (st + dr) / 2;
		if (v[mid] >= k)
		{
			val = mid;
			dr = mid - 1; // caut mai departe in stanga
		}
		else
		{
			st = mid + 1;
		}
	}
	return val;
}

int main()
{

	in >> n;
	for (i = 0; i < n; i++)
		in >> v[i];

	in >> m;
	for (i = 0; i < m; i++)
	{
		int a, b;
		int raspuns;
		in >> a >> b;
        
        // in functie de tipul cerintei apelez functia respectiva si afisez raspunsul
		if (a == 0)
			raspuns = caz0(b);
		if (a == 1)
			raspuns = caz1(b);
		if (a == 2)
			raspuns = caz2(b);

        out << raspuns << '\n';
	}
	return 0;
}