#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) {
			if (a[exact(x)] == x)
				fout << exact(x) << '\n';
			else
				fout << -1 << '\n';
		}
		if (aux == 1)
			fout << upper(x) << '\n';
		if (aux == 2)
			fout << lower(x) << '\n';
	}
	fin.close();
	fout.close();
}

int exact(int x) {
	int i = 0, j = n;
	while (i <= j) {
		int mid = (i + j) / 2;
		if (a[mid] <= x)
			i = mid + 1;
		if (a[mid] > x)
			j = mid - 1;
	}
	return j;
}

int upper(int x) {
	int i = 0, j = n;
	while (i <= j) {
		int mid = (i + j) / 2;
		if (a[mid] <= x)
			i = mid + 1;
		if (a[mid] > x)
			j = mid - 1;
	}
	return j;
}

int lower(int x) {
	int i = 0, j = n;
	while (i <= j) {
		int mid = (i + j) / 2;
		if (a[mid] < x)
			i = mid + 1;
		if (a[mid] >= x)
			j = mid - 1;
	}
	return i;
}