#include <stdio.h>

using namespace std;

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

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

long n,m;
long valori[MAX];

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

int main()
{
 long i,op,x;
 
 fscanf(fin,"%ld",&n); 
 for (i=1;i<=n;i++)
  fscanf(fin,"%ld",&valori[i]);
   
 fscanf(fin,"%ld",&m); 
 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%ld %ld\n",&op,&x);
  
  if (!op)
   fprintf(fout,"%ld\n",caut0(x));
  else 
   if (op==1) 
    fprintf(fout,"%ld\n",caut1(x));
   else
    if (op==2)
     fprintf(fout,"%ld\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;
}