#include <iostream.h>
#include <fstream.h>

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

ifstream fin(IN);
ofstream fout(OUT);

long n,m;
long valori[MAX];

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

int main()
{
 long i, op, x;

 fin>>n;
 
 for (i = 1; i <= n; i++)
  fin>>valori[i];
  
 fin>>m;
 
 for (i = 1; i <= m; i++)
 {
  fin>>op>>x;
  
  if (!op)
   fout<<caut0(x)<<endl;
  else 
   if (op == 1) 
    fout<<caut1(x)<<endl;
   else
    if (op == 2)
     fout<<caut2(x)<<endl;
 }
 fin.close();
 fout.close();
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;
}