#include<fstream>
using namespace std;
int a[100005];
int n, m;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int cautbin0(int val)
{
	int l = 1, r = n, pos = n + 1;
	while (l <= r)
	{
		int m = (l + r) / 2;
		if (val >= a[m])
		{
			l = m + 1;
			pos = m;
		}
		else
			{
				r = m - 1;
			}
			
	}
	return pos;
}
int cautbin2(int val)
{
	int l = 1, r = n, pos = n + 1;
	while (l <= r)
	{
		int m = (l + r) / 2;
		if (val <= a[m])
		{
			r = m - 1;
			pos = m;
		}
		else
		{
			l = m + 1;
		}

	}
	return pos;
}

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++)
		f >> a[i];
	f >> m;
	while (m--)
	{
		int op, val;
		f >> op >> val;
		if (op == 0)
		{
			int pos = cautbin0(val);
			if (a[pos] == val)
				g << pos;
			else
				g << -1;
		}
		else
		if (op == 1)
		{
			g << cautbin0(val);
		}
		else
		if (op == 2)
		{
			g << cautbin2(val);
		}
		g << '\n';
	}
}