// http://infoarena.ro/problema/cautbin

#include <cstdio>

int *Array;
int n, m;

int binarySearch(int type, int key) {
// 0 x - pozitia cea mai mare pe care se afla elementul cu valoarea x sau -1 daca nu se gaseste in sir
// 1 x - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir
// 2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu x in sir

	int left = 0, right = n - 1, mid, ans = -1;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (Array[mid] < key) {
			if (type == 1)
				ans = mid;
			left = mid + 1;
		}
		if (Array[mid] == key)
			return mid + 1;
		if (Array[mid] > key) {
			if (type == 2)
				ans = mid;
			right = mid - 1;
		}
	}
	if (ans == -1)
		return ans;
	return ans + 1;
}

int main() {

	freopen("cautbin.in", "r", stdin), freopen("cautbin.out", "w", stdout);

	scanf("%d", &n);
	Array = new int[n];

	int i;
	for (i = 0; i < n; ++ i)
		scanf("%d", &Array[i]);

	scanf("%d", &m);
	int type, key;
	for (i = 0; i < m; ++ i) {
		scanf("%d %d", &type, &key);
		printf("%d\n", binarySearch(type, key));
	}
	
	delete Array;

	return 0;
}