#include <fstream>
const int MAX = 100001;

using namespace std;

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

int n, v[MAX], m, cer, x;

int cer1(int x) {
	int left = 1, right = n, poz = -1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (v[mid] == x) poz = mid;
		if (x >= v[mid]) left = mid + 1;
		else right = mid - 1;
	}
	return poz;
}

int cer2(int x) {
	int left = 1, right = n, poz = -1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (x >= v[mid]) left = mid + 1, poz = mid;
		else right = mid - 1;
	}
	return poz;
}

int cer3(int x) {
	int left = 1, right = n, poz = -1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (x <= v[mid]) right = mid - 1, poz = mid;
		else left = mid + 1;
	}
	return poz;
}

void problema() {
	in >> n;
	for (int i = 1; i <= n; i++)in >> v[i];
	in >> m;
	while (m--) {
		in >> cer >> x;
		if (cer == 0) out << cer1(x) << '\n';
		else if (cer == 1)out << cer2(x) << '\n';
		else out << cer3(x) << '\n';
		   
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);
   
	problema();
	
	return 0;
}