# include <stdio.h>
# include <vector>
# include <algorithm>

int main(void) {
	
	FILE *fin = fopen("cautbin.in", "r");
	FILE *fout = fopen("cautbin.out", "w");

	int N, Q, op, x, res;
	std::vector<int>::iterator it;
	std::vector<int> v;

	fscanf(fin, "%d", &N);
	for (int i = 0; i < N; i++) {
		fscanf(fin, "%d", &x);
		v.push_back(x);
	}

	fscanf(fin, "%d", &Q);
	for (int i = 0; i < Q; i++) {
		fscanf(fin, "%d%d", &op, &x);

		switch (op)
		{
		case 0:
			if (!std::binary_search(v.begin(), v.end(), x))
				res = -1;
			else {
				it = std::upper_bound(v.begin(), v.end(), x);
				res = it - v.begin();
			}
			break;
			
		case 1:
			it = std::upper_bound(v.begin(), v.end(), x);
			res = it - v.begin();
			break;

		case 2:
			it = std::lower_bound(v.begin(), v.end(), x);
			res = it - v.begin() + 1;
			break;

		default:
			break;
		}

		fprintf(fout, "%d\n", res);
	}

	fclose(fin);
	fclose(fout);

	return 0;
}