#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n;

vector<int> v;



int find0(int x)
{

	int rightest = -2;
	int st, dr;
	st = 0;
	dr = n - 1;

	while (st <= dr)
	{
		int mid = st + (dr - st) / 2;
		if (v[mid] == x)
			rightest = mid;
		if (x < v[mid])
		{
			dr = mid - 1;
		}
		else if (v[mid] <= x)
		{
			st = mid + 1;
		}
	}
	return rightest + 1;

}

int find1(int x)
{

	int rightest = -2;
	int st, dr;
	st = 0;
	dr = n - 1;

	while (st <= dr)
	{
		int mid = st + (dr - st) / 2;
		if (v[mid] <= x)
			rightest = mid;
		if (x < v[mid])
		{
			dr = mid - 1;
		}
		else if (v[mid] <= x)
		{
			st = mid + 1;
		}
	}
	return rightest + 1;

}

int find2(int x)
{
	int leftest = -2;
	int st, dr;
	st = 0;
	dr = n - 1;

	while (st <= dr)
	{
		int mid = st + (dr - st) / 2;
		if (v[mid] >= x)
			leftest = mid;
		if (x <= v[mid])
		{
			dr = mid - 1;
		}
		else if (v[mid] < x)
		{
			st = mid + 1;
		}
	}
	return leftest + 1;
}


int find(int q, int x)
{
	switch (q) {
	case 0:return find0(x);
	case 1:return find1(x);
	default:return find2(x);
	}
}

int main()
{
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");

	in >> n;

	v.resize(n);

	for (int i = 0; i < n; ++i)
		in >> v[i];

	int m;
	in >> m;
	for (int i = 0; i < m; ++i)
	{
		int q, x;
		in >> q >> x;
		out << find(q, x) << "\n";

	}

	return 0;
}