#include <fstream>

int nA[100010];

int absearch(int *a, int l, int r, int caut)
{
	int m;
	while(l <= r)
	{
		m = (r + l) / 2;
		if(a[m] <= caut)
			l = m + 1;
		else
			r = m - 1;
	}
	m = (r + l) / 2;
	if(a[m] > caut) m--;
	if(a[m] == caut) return m;
	return -1;
}

int bbsearch(int *a, int l, int r, int caut)
{
	int m;
	while(l < r)
	{
		m = (r + l) / 2;
		if(a[m] <= caut)
			l = m + 1;
		else
			r = m;
	}
	m = (r + l) / 2;
	if(a[m] > caut) m--;
	return m;
}

int cbsearch(int *a, int l, int r, int caut)
{
	int m;
	while(l < r)
	{
		m = (r + l) / 2;
		if(a[m] < caut)
			l = m + 1;
		else
			r = m;
	}
	m = (r + l) / 2;
	if(a[m] < caut) m++;
	return m;
}

int main(void)
{
	int nV, nM, a, b;
	std::ifstream in("cautbin.in");
	std::ofstream out("cautbin.out");
	in >> nV;
	for(int i(1); i <= nV; i++)
		in >> nA[i];
	in >> nM;
	for(int i(0); i < nM; i++)
	{
		in >> a >> b;
		if(a == 0) out << absearch(nA, 1, nV, b) << "\n";
		if(a == 1) out << bbsearch(nA, 1, nV, b) << "\n";
		if(a == 2) out << cbsearch(nA, 1, nV, b) << "\n";
	}
	return 0;
}