#include <fstream>
using namespace std;
string file = "cautbin";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
int v[100000], n;

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

	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if (v[mid] >= val)
		{
			dr = mid - 1;
		}
		else
		{
			st = mid + 1;
		}
	}
	return st;
}
int main()
{
	int m, x, c;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	cin >> m;
	while (m)
	{
		cin >> c >> x;
		cout << cb(c, x) << '\n';
		m--;
	}
}