#include<fstream>
#include<iostream>
#define MAX 100005
using namespace std;

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

int a[MAX], n, m, t, val;

int cb(int val)
{
	int st = 0, dr = n - 1, mid = -1;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (a[mid] <= val)
			st = mid + 1;
		else
			dr = mid - 1;
	}
	if (a[dr] == val)
		return dr + 1;
	return -1;
}

int cb1(int val)
{
	int st = 0, dr = n - 1, mid = -1;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (a[mid] <= val)
			st = mid + 1;
		else
			dr = mid - 1;
	}
	return dr + 1;
}

int cb2(int val)
{
	int st = 0, dr = n - 1, mid = -1;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (a[mid] >= val)
			dr = mid - 1;
		else
			st = mid + 1;
	}
	return st + 1;
}
int main()
{
	f >> n;
	for (int i = 0; i < n; ++i)
	{
		f >> a[i];
	}
	f >> m;
	for (int i = 0; i < m; ++i)
	{
		f >> t >> val;
		if (t == 0)
		{
			g << cb(val) << '\n';
		}
		else if (t == 1)
		{
			g << cb1(val) << '\n';
		}
		else
		{
			g << cb2(val) << '\n';
		}
	}
}