#include <cstdio>

#define maxN 100005

using namespace std;

FILE *f = fopen ("cautbin.in","r");
FILE *g = fopen ("cautbin.out","w");

int n, m, a[maxN];

int bsearch0(int val)
{
	int lo = 1, hi = n, mid;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (a[mid] <= val)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	if (a[mid] > val)
		mid--;
	if (a[mid] == val)
		return mid;
	return - 1;
}

int bsearch1(int val)
{
	int lo = 1, hi = n, mid;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (a[mid] <= val)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	if (a[mid] > val)
		mid--;
	return mid;
}

int bsearch2(int val)
{
	int lo = 1, hi = n, mid;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (a[mid] >= val)
			hi = mid - 1;
		else
			lo = mid + 1;
	}
	if (a[mid] < val)
		mid++;
	return mid;
}

int main()
{
	int op, val;
	
	fscanf (f, "%d", &n);
	for (int i = 1; i <= n; i++)
		fscanf (f, "%d", &a[i]);
	
	fscanf (f, "%d", &m);
	for (int i = 1; i <= m; i++) {
		fscanf (f, "%d%d", &op, &val);
		switch (op) {
		case 0 : fprintf (g, "%d\n", bsearch0(val) ); break;
		case 1 : fprintf (g, "%d\n", bsearch1(val) ); break;
		case 2 : fprintf (g, "%d\n", bsearch2(val) ); break;
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}