#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==0)
   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;
}