#include <fstream>
#include <algorithm>

using namespace std;

const int MAXN = 100009;
int v[MAXN];

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

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

int binSearchLeftmost(int left, int right, int x) {
	if(right - left == 1) {
		return right;
	}
	else {
		int mid = right - (right - left) / 2;
		if(x > v[mid])	return binSearchLeftmost(mid, right, x);
		else			return binSearchLeftmost(left, mid, x);
	}
}


int main() {
	int n, m, i, op, x;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f >> n;
	for(i = 0; i < n; ++i) {
		f >> v[i];
	}
	f >> m;
	for(i = 0; i < m; ++i) {
		f >> op >> x;
		switch(op) {
		case 0:
			g << 1 + binSearchRightmostOrDie(0, n, x) << '\n';
			break;
		case 1:
			g << 1 + binSearchRightmost(0, n, x) << '\n';
			break;
		case 2:
			g << 1 + binSearchLeftmost(-1, n - 1, x) << '\n';
			break;
		}
	}
	f.close();
	g.close();
	return 0;
}