#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 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 main()
{
	read();

	while(m--)
	{
		in >> p >> x;
		if(p == 0)
		{
			int ans = upper_bound(x);
			out << (a[ans] == x ? ans : -1);
		}
		else if(p == 1) out << upper_bound(x);
		else out << upper_bound(x-1) + 1;
		out << '\n';
	}

	return 0;
}