#include <cstdio>
#include <algorithm>
using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}
int n;
int A[100000];

int f1(int value) {
	if (value < A[0] || A[n - 1] < value) {
		return -1;
	}
	int lo = 0, hi = n;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		if (A[mid] <= value) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	return A[lo] == value ? lo + 1 : -1;
}

int f2(int value) {
	int lo = 0, hi = n;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		if (A[mid] <= value) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	return lo + 1;
}

int f3(int value) {
	int lo = -1, hi = n - 1;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		if (A[mid] >= value) {
			hi = mid;
		} else {
			lo = mid;
		}
	}
	return hi + 1;
}

int main() {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	n = next_int();
	for (int i = 0; i < n; i++) {
		A[i] = next_int();
	}
	int m = next_int();
	for (int i = 0; i < m; i++) {
		int a = next_int();
		int b = next_int();
		if (a == 0) {
			printf("%d\n", f1(b));
		}
		if (a == 1) {
			printf("%d\n", f2(b));
		}
		if (a == 2) {
			printf("%d\n", f3(b));
		}
	}
	return 0;
}