#include <cstdio>

using namespace std;

#define IN "cautbin.in"
#define OUT "cautbin.out"
#define MAX 100011

long n,m;
long valori[MAX];

long caut0(long );
long caut1(long );
long caut2(long );

int main()
{
 long i, op, x;
 
 freopen( IN, "r", stdin );
 freopen( OUT, "w", stdout );

 scanf("%d", &n); 
 for (i = 1; i <= n; i++)
  scanf("%d", valori+i);
   
 scanf("%d", &m); 
 for (i = 1; i <= m; i++)
 {
  scanf("%d %d\n", &op, &x);
  
  if (!op)
   printf("%d\n", caut0(x));
  else 
   if (op == 1) 
    printf("%d\n", caut1(x));
   else
    if (op == 2)
     printf("%d\n", caut2(x));
 }
return 0;
}

long caut0(long x)
{
	long st, dr, med;
	st = 1; dr = n;
	med = (st + dr) / 2;
	while (st <= dr)
	{
		if (valori[med] == x && (valori[med + 1] >= x || med + 1 > n)) return med;
		else if (valori[med + 1] <= x) st = med + 1;
		else if (valori[med + 1] > x) dr = med - 1;
		med = (st + dr) / 2;
	}
	return -1;
}

long caut1(long x)
{
	long st, dr, med;
	st = 1; dr = n; med = (st + dr) / 2;
	while (st <= dr)
	{
		if (valori[med] <= x && (valori[med + 1] > x || med + 1 > n)) return med;
		else if (valori[med + 1] <= x) st = med + 1;
		else dr = med - 1;
		med = (st + dr) / 2;
	}
	return med;
}

long caut2(long x)
{
	long st, dr, med;
	st = 1; dr = n; med = (st + dr) / 2;
	while (st <= dr)
	{
		if (valori[med] >= x && (valori[med - 1] < x || med - 1 < 1)) return med;
		else if (valori[med - 1] >= x) dr = med - 1;
		else st = med + 1;
		med = (st + dr) / 2;
	}
	return med;
}