#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

int N, Q, v[100010];

int main()
{
	in >> N;

	for (int i = 1;i <= N;++i)
		in >> v[i];

	in >> Q;

	for (int i = 1;i <= Q;++i)
	{
		int o, x;

		in >> o >> x;

		if (o == 0)
		{
			int p = upper_bound(v + 1, v + N + 1, x) - v;
			if (p != N + 1 && p - 1 != 0 && v[p - 1] == x)
				out << p - 1 << '\n';
			else
				out << "-1\n";
		}
		else if (o == 1)
		{
			int p = upper_bound(v + 1, v + N + 1, x) - v;

			if (p - 1 != 0 && v[p - 1] == x)
				out << p - 1 << '\n';
			else
				out << p << '\n';

		}
		else
		{
			int p = lower_bound(v + 1, v + N + 1, x) - v;

			if (p +1 != N+1 && v[p] == x)
				out << p  << '\n';
			else
				out << p-1 << '\n';

		}

	}



	return 0;


}