#include <iostream>
#include <stdio.h>

using namespace std;

int m, n, v[100005];

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

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

int bsearch2 (int x) {
	int l = 0, r = n+1;
	
	while (r - l > 1) {
		int mid = (l + r) / 2;
		
		if (x <= v[mid]) {
			r = mid;
		} else {
			l = mid;
		}
	}
	
	return r;
}
	
int main (void) {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		int x, c;
		scanf("%d%d", &c, &x);
		
		if (c == 0) {
			printf("%d\n", bsearch0(x));
		} else if (c == 1) {
			printf("%d\n", bsearch1(x));
		} else {
			printf("%d\n", bsearch2(x));
		}
	}
	
	return 0;
}