#include <stdio.h>
#include <stdlib.h>

int N;
int data[100001];

static
int binarySearch(int key) {
	int result = -1;

	int inf = 0, sup = N - 1;

	if (data[sup] == key) return sup;

	while (inf <= sup) {
		int mid = inf + (sup - inf) / 2;

		if (data[mid] == key && data[mid + 1] > key) {
			result = mid;
			break;
		}

		if (data[mid] <= key) {
			inf = mid + 1;
		} else {
			sup = mid - 1;
		}
	}
	return result;
}

static
int biggestPositionLessThanEqual(int k) {
	int result = -1;

	int inf = 0, sup = N - 1;

	if (k < data[inf])
		return -1;

	while (inf <= sup) {
		int mid = inf + (sup - inf) / 2;
		if (data[mid] > k) {
			sup = mid - 1;
		} else {
			// data[mid] <= k
			if (data[mid + 1] > k) {
				if  (data[mid] == k) {
					result = mid;
				}
				else {
					result = mid + 1;
				}
				break;
			}
			else {
				// data[mid + 1] >= k
				inf = mid + 1;
			}
		}
	}

	return result;
}


static
int smallestPositionGreaterThanEqual(int k) {
	int result = -1;

	int inf = 0, sup = N - 1;

	if (data[sup] < k)
		return sup + 1;

	while (inf <= sup) {
		int mid = inf + (sup - inf) / 2;
		if (data[mid] < k) {
			// data[mid] < k
			if (data[mid + 1] >= k) {
				result = mid + 1;
				break;
			}
			else {
				inf = mid + 1;
			}
		}
		else {
			// data[mid] >= k
			sup = mid;
		}
	}

	return result;
}

int main(int argc, char **argv) {
	int M;
	int i, result, q, x;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", data + i);
	}

	scanf("%d", &M);

	for (i = 0; i < M; i++) {
		scanf("%d %d", &q, &x);
		if (q == 0)
			result = binarySearch(x);
		else if (q == 1)
			result = biggestPositionLessThanEqual(x);
		else
			result = smallestPositionGreaterThanEqual(x);

		if (result != -1)
			++result;
		printf("%d\n", result);
	}
	return 0;
}