#include <iostream>
#include <fstream>

std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");

int binary_search_rightmost(int start, int end, int val, int v[])
{
	int low = start;
	int hi = end;
	while (low <= hi)
	{
		int mid = low + (hi - low) / 2;
		if (v[mid] > val)
			hi = mid - 1;
		else
			low = mid + 1;
	}
	return (low - 1 >= 0 && v[low - 1] == val) ? low /* low-1+1 */ : -1;
}

int search_smaller_or_equal(int start, int end, int val, int v[])
{
	int low = start;
	int hi = end;
	while (low <= hi)
	{
		int mid = low + (hi - low) / 2;
		if (v[mid] > val)
			hi = mid - 1;
		else
			low = mid + 1;
	}
	return (low - 1 >= 0 && v[low - 1] <= val) ? low /* low-1+1 */ : -1;
}

int search_bigger_or_equal(int start, int end, int val, int v[])
{
	int low = start;
	int hi = end;
	while (low < hi)
	{
		int mid = low + (hi - low) / 2;
		if (v[mid] < val)
			low = mid + 1;
		else
			hi = mid;
	}
	return v[low] >= val ? low + 1: -1;
}

int v[100000],m,n;

int main()
{
	f >> n;
	for (int i = 0; i < n; ++i)
		f >> v[i];

	f >> m;
	for (int i = 0; i < m; ++i)
	{
		int tip, x;
		f >> tip >> x;
		if (tip == 0)
			g << binary_search_rightmost(0, n - 1, x, v)<< '\n';
		else
		if (tip == 1)
			g << search_smaller_or_equal(0, n - 1, x, v) << '\n';
		else
			g << search_bigger_or_equal(0, n - 1, x, v) << '\n';
	}
}