#include<stdio.h>

int v[10000];

int search0(int f, int l, int x) {
	int m;

	while (f <= l) {
		m = f + (l - f) / 2;
		if ( v[m] < x) 
			l = m - 1;
		else
			f = m + 1;
	}
	if (v[m] > x)
		m--;
	if (v[m] != x)
		return -1;
	return m;
}
int search1(int f, int l, int x) {
	int m;

	while (f <= l) {
		m = f + (l - f) / 2;
		if ( v[m] < x) 
			l = m - 1;
		else
			f = m + 1;
	}
	if (v[m] > x)
		m--;
	return m;
}

int search2(int f, int l, int x) {
	int m;

	while (f <= l) {
		m = f + (l - f) / 2;
		if ( v[m] <= x) 
			l = m - 1;
		else
			f = m + 1;
	}

	if (v[m] < x)
		m++;
	return m;
}


int main() {
	

	int n, i;
	int t, x, c, r;
	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", &t);
	for (i = 0; i < t; i++) {
		scanf("%d %d", &c, &x);
		switch(c) {
			case 0:
				r = search0(1, n, x);
				break;
			case 1:
				r = search1(1, n, x);
				break;
			case 2:
				r = search2(1, n, x);
				break;
		}
		printf("%d\n", r);
	}

	return 0;
}