#include <stdio.h>

#define infile "cautbin.in"
#define outfile "cautbin.out"

#define NMAX 100001

FILE *fin, *fout;
int s[NMAX], n;


//cea mai mare pozitie pe care se afla un elem cu val x sau -1
int binary_search0(int x) {
	int left, right, m;

	right = 1; left = n;

	while (right <= left) {
		m = (right + left) / 2;
		
		if (s[m] <= x)
			right = m + 1;
		else
			left = m - 1;
	}

	right--;
	if (s[right] == x) return right;

	return -1;
}

//cea mai mare pozitie pe care se afla un elem <= x
int binary_search1(int x) {
	int left, right, m;

	right = 1; left = n;

	while (right <= left) {
		m = (right + left) / 2;
		
		if (s[m] <= x)
			right = m + 1;
		else
			left = m - 1;
	}

	right--;
	if (s[right] <= x) return right;

	return 0;
}

//cea mai mica pozitie pe care se afla un elem >= x
int binary_search2(int x) {
	int left, right, m;

	right = 1; left = n;

	while (right <= left) {
		m = (right + left) / 2;
		
		if (s[m] < x)
			right = m + 1;
		else
			left = m - 1;
	}

	left++;
	if (s[left] >= x) return left;

	return 0;
}

int main() {
	int i, m, code, x;

	fin = freopen(infile, "r", stdin);
	fout = freopen(outfile, "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &s[i]);
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d", &code, &x);
		switch(code) {
			case 0:
				printf("%d\n", binary_search0(x));
				break;
			case 1:
				printf("%d\n", binary_search1(x));
				break;
			case 2:
				printf("%d\n", binary_search2(x));
				break;
		}


	}

	return 0;
}