/* int i pas=(1<<k) 
for(i=0;pas!=0 ;pas/=2) pass >>=1
if(i+pas are prop )
i+=pas;
i este ultimul cu prop 
*/
#include <stdio.h>
using namespace std;

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

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 (v[mijl] <= x)
			st = mijl;
		else
			dr = mijl - 1;
	}
	if (v[st] > x)
		return st - 1;
	return st;
}

int cauta2 (int x)
{
	int st, dr, mijl;
	st = 1;
	dr = n;
	while (st != dr)
	{
		mijl = st + (dr - st) / 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)
		{
			sol = cauta0 (nr);
			fprintf (g,"%d\n", sol);
		}
		else if (val == 1)
		{
			sol = cauta1 (nr);
			fprintf (g,"%d\n", sol);
		}
		else if (val == 2)
		{
			sol = cauta2 (nr);
			fprintf (g,"%d\n", sol);
		}
	}
	
	fclose(g);
	fclose(f);
	return 0;
}