#include<fstream>
using namespace std;

void read();
int exact(int x);
int upper(int x);
int lower(int x);

int n, m;
int a[100005];

int main() {
	read();
	return 0;
}

void read() {
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> a[i];
	fin >> m;
	for (int j = 1; j <= m; ++j) {
		int aux, x;
		fin >> aux >> x;
		if (aux == 0) fout << exact(x) << '\n';
		if (aux == 1) fout << upper(x) << '\n';
		if (aux == 2) fout << lower(x) << '\n';
	}
	fin.close();
	fout.close();
}

int exact(int x) {
	int step, i;
	for (step = 1; step << 1 <= n; step <<= 1);
	for (i = 0; step; step >>= 1)
		if (i + step <= n && a[i + step] <= x)
		{
			i += step;
			if (a[i] == x)
				return i;
		}
	return -1;
}

int upper(int x) {
	int step, i;
	for (step = 1; step << 1 <= n; step <<= 1);
	for (i = 0; step; step >>= 1)
		if (i + step <= n && a[i + step] <= x)
			i += step;
	return i;
}

int lower(int x) {
	int step, i;
	for (step = 1; step << 1 <= n; step <<= 1);
	for (i = n; step; step >>= 1)
	{
		if (i - step >= 1 && a[i - step] >= x)
			i -= step;
	}
	return i;
}