#include <stdio.h>
using namespace std;

int v[100001];
int m, n, i, j;
int nr, val;

int cauta0 (int x)
{
	int st, dr, mijl;
	st = 1;
	dr = n;
	while (st != dr)
	{
		mijl = (1 + st + dr) / 2;
		if (x >= v[mijl])
			st = mijl;
		else
			dr = mijl - 1;
	}
	if (v[st] == x)
		return st;
	return -1;
}

int cauta1 (int x)
{
	int st, dr, mijl;
	st = 1;
	dr = n;
	while (st != dr)
	{
		mijl = (1 + st + dr) / 2;
		if (x >= v[mijl])
			st = mijl;
		else
			dr = mijl - 1;
	}
	if (v[st] > x)
		return st - 1;
	return -1;
}

int cauta2 (int x)
{
	int st, dr, mijl;
	st = 1;
	dr = n;
	while (st != dr)
	{
		mijl = (1 + st + dr) / 2;
		if (v[mijl] >= x)
			dr = mijl;
		else
			st = mijl + 1;
	}
	if (v[st] < x)
		return st + 1;
	return st;
}

int main ()
{
	FILE *f = fopen ("cautbin.in","r");
	FILE *g = fopen ("cautbin.out","w");
	fscanf (f,"%d", &n);
	for (i=1; i<=n; ++i)
		fscanf (f,"%d", &v[i]);
	fscanf (f,"%d", &m);
	
	for (i=1; i<=m; ++i)
	{
		fscanf (f,"%d %d", &val, &nr);
		if (val == 0)
			fprintf (g,"%d\n", cauta0 (nr));
		else if (val == 1)
			fprintf (g,"%d\n", cauta1(nr));
		else if (val == 2)
			fprintf (g,"%d\n", cauta2(nr));
	}
	
	fclose(g);
	fclose(f);
	return 0;
}