#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
#define MAX 100000
int N;
int v[MAX];

int BinarySearch0(int x)
{
	int p = 0, q = N;
	while (p + 1 < q)
	{
		int m = (p + q) / 2;
		(v[m] <= x ? p : q) = m; 
	}
	return v[p] == x ? p + 1 : -1;
}
int BinarySearch1(int x)
{
	int p = 0, q = N;
	while (p + 1 < q)
	{
		int m = (p + q) / 2;
		(v[m] > x ? q : p) = m;
	}
	return p + 1;
}
int BinarySearch2(int x)
{
	int p = 0, q = N;
	while (p + 1 < q)
	{
		int m = (p + q) / 2;
		if (v[m] >= x)
		{
			if (m == 0 || v[m - 1] < x)
				return m + 1;
			q = m;
		}
		else
		{
			p = m;
		}
	}
	return p + 1;
}
int main()
{
	in >> N;
	for (int i = 0; i < N; i++)
	{
		in >> v[i];
	}
	int M;
	in >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		in >> a >> b;
		switch (a)
		{
		case 0:
			out << BinarySearch0(b) << '\n';
			break;
		case 1:
			out << BinarySearch1(b) << '\n';
			break;
		case 2:
			out << BinarySearch2(b) << '\n';
			break;
		}
	}
}