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

int n, m, v[100000];

int main() {
	int i, t, val;
	
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	scanf("%d", &m);
	
	//sort(v + 1, v + n + 1);
	
	while(m--) {
		scanf("%d%d", &t, &val);
		switch(t) {
			case 0: {
				if(!binary_search(v + 1, v + 1 + n, val)) {
					printf("-1\n");
					break;
				}
				printf("%d\n", (upper_bound(v + 1, v + n + 1, val) - v - 1) );
				break;
			}
			case 1: {
				printf("%d\n", (lower_bound(v + 1, v + n + 1, val + 1) - v - 1) );
				break;
			}
			case 2: {
				printf("%d\n", (upper_bound(v + 1, v + n + 1, val - 1) - v) );
				break;
			}
		}	
	}
	
	return 0;
}