#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n;
int a[100005];

int main()
{
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> a[i];

	int q, tip, x;
	fin >> q;
	for (int i = 1; i <= q; i++)
	{
		int st = 0, dr = n + 1;
		fin >> tip >> x;
		if (tip == 0)
		{
			int poz = -1;
			while (dr - st > 1)
			{
				int mij = st + (dr - st) / 2;
				if (a[mij] == x)
					poz = mij;
				if (a[mij] <= x)
					st = mij;
				else dr = mij;
			}
			fout << poz << '\n';
		}
		else if (tip == 1)
		{
			while (dr - st > 1)
			{
				int mij = st + (dr - st) / 2;
				if (a[mij] <= x)
					st = mij;
				else dr = mij;
			}
			fout << st << '\n';
		}
		else
		{
			while (dr - st > 1)
			{
				int mij = st + (dr - st) / 2;
				if (a[mij] >= x)
					dr = mij;
				else st = mij;
			}
			fout << dr << '\n';
		}
	}
	return 0;
}