#include <fstream>
using namespace std;

int last_le(int x, int v[], int l_o, int r_i) {
	do {
		int m = (l_o + r_i + 1) / 2;
		if (v[m] <= x)
			l_o = m;
		else
			r_i = m-1;
	} while (l_o < r_i);
	return l_o; /* == r_i */
}
int first_ge(int x, int v[], int l_i, int r_o) {
	do {
		int m = (l_i + r_o) / 2;
		if (v[m] < x)
			l_i = m + 1;
		else
			r_o = m;
	} while (l_i < r_o);
	return l_i; /* == r_o */
}

int main() {
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	int n, *v, m, op, x, tmp;
	in>>n;
	v = new int[m];
	for (int i = 0; i < n; i++)
		in>>v[i];
	in>>m;
	for (int i = 0; i < m; i++) {
		in>>op>>x;
		switch (op) {
		case 0: tmp = last_le(x, v, -1, n - 1);
				out<<(tmp >= 0 ? (v[tmp] == x ? tmp : -1) : -1) + 1<<endl; break;
		case 1: out<<last_le(x, v, -1, n - 1) + 1<<endl; break;
		case 2: out<<first_ge(x, v, 0, n) + 1<<endl; break;
		}
	}
	in.close();
	out.close();
	return 0;
}