#include <fstream>

using namespace std;

int a[100001];

int caut0x(int st, int dr, int x) {
	int mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (a[mij] <= x) st = mij + 1;
		else dr = mij - 1;
	}
	mij = (st + dr) / 2;
	if (a[mij] > x) mij--;
	if (a[mij] == x) return mij;
	else return -1;
}

int caut1x(int st, int dr, int x) {
	int mij;
	while (st < dr) {
		mij = (st + dr) / 2;
		if (a[mij] <= x) st = mij + 1;
		else dr = mij;
	}
	mij = (st + dr) / 2;
	if (a[mij] > x) mij--;
	return mij;
}

int caut2x(int st, int dr, int x) {
	int mij;
	while (st < dr) {
		mij = (st + dr) / 2;
		if (a[mij] >= x) dr = mij;
		else st = mij + 1;
	}
	mij = (st + dr) / 2;
	if (a[mij] < x) mij++;
	return mij;
}

int main() {
	int n, m, x, y;
	ifstream in ("cautbin.in");
	ofstream out("cautbin.out");
	in >> n;
	for (int i = 1; i <= n; i++)
		in >> a[i];
	
	in >> m;
	
	for (int i = 1; i <= m; i++) {
		in >> y >> x;
		if (y == 0) out << caut0x(1, n, x) << "\n";
		if (y == 1) out << caut1x(1, n, x) << "\n";
		if (y == 2) out << caut2x(1, n, x) << "\n";
	}
	return 0;
}