#include <fstream>
using namespace std;

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

int n, m, p, x;
int a[100'001];

void read()
{
	in >> n;
	for(int i = 1; i <= n; ++i)
		in >> a[i];
	in >> m;
}

int caut(int x)
{
	int index = 0;
	for(int bit = 17; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] > x)
			index -= (1<<bit);
	}

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

int upper_bound(int x)
{
	int index = 0;
	for(int bit = 16; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] > x)
			index -= (1<<bit);
	}

	return index;
}

int lower_bound(int x)
{
	int index = 0;
	for(int bit = 16; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] >= x)
			index -= (1<<bit);
	}

	return index+1;

}



int main()
{
	read();

	while(m--)
	{
		in >> p >> x;
		if(p == 0) out << caut(x);
		else if(p == 1) out << upper_bound(x);
		else out << lower_bound(x);
		out << '\n';
	}

	return 0;
}