#include <stdio.h>

int v[100005], N, M;

int bsearch0 (int x) {
	int l = 1, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (v[mid] <= x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	
	return (v[l-1] == x) ? l-1 : -1;
}

int bsearch1 (int x) {
	int l = 1, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (v[mid] <= x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	
	return l-1; 
}

int bsearch2 (int x) {
	int l = 1, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (v[mid] >= x) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	return r; 
}

int main (void) {
	freopen("cautbin.in", "r", stdin);
	freopen("coutbin.out", "w", stdout);
	
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &v[i]);
	}
	
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
		int c, x;
		scanf("%d %d", &c, &x);
		switch (c) {
			case 0: printf("%d\n", bsearch0(x)); break;
			case 1: printf("%d\n", bsearch1(x)); break;
			case 2: printf("%d\n", bsearch2(x)); break;
		}
	}
	
	return 0;
}