#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;

const string txt = "cautbin";
const int nmax = 1e5 + 5;

ifstream f(txt + ".in");
ofstream g(txt + ".out");

int n, q, v[nmax];

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

	int lg = 0;
	while ((1 << lg) <= n) lg++;
	f >> q;
	for (int i = 1; i <= q; i++)
	{
		int tip, x; f >> tip >> x;
		
		if (tip == 0)
		{
			int ans = 0;
			for (int j = lg; j >= 0; j--)
			{
				int poz = ans + (1 << j);
				if (poz > n) continue;

				if (v[poz] <= x) ans = poz;
			}

			g << (v[ans] == x ? ans : -1) << '\n';
		}

		else if (tip == 1)
		{
			int ans = 0;
			for (int j = lg; j >= 0; j--)
			{
				int poz = ans + (1 << j);
				if (poz > n) continue;

				if (v[poz] <= x) ans = poz;
			}

			g << ans << '\n';
		}

		else
		{
			int ans = 0;
			for (int j = lg; j >= 0; j--)
			{
				int poz = ans + (1 << j);
				if (poz > n) continue;

				if (v[poz] < x) ans = poz;
			}

			g << ans + 1 << '\n';
		}
	}
	return 0;
}