#include<stdio.h>

#define nmax 100001
#define IN "cautbin.in"
#define OUT "cautbin.out"

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

int v[nmax];
int i,n,m,x;
	
int binar0(int v[], int n, int x);
int binar1(int v[], int n, int x);	
int binar2(int v[], int n, int x);
	
int main()
{
 fscanf(fin,"%d",&n);
 for(i=1;i<=n;i++)
  fscanf(fin,"%d ",&v[i]);

 fscanf(fin,"%d",&m);

 while(m--)
 {
  fscanf(fin,"%d %d",&i,&x);
  if(!i) 
   fprintf(fout,"%d\n",binar0(v,n,x));
  else
   if(i==1)
    fprintf(fout,"%d\n",binar1(v,n,x));
  else 
   if(i==2) 
    fprintf(fout,"%d\n",binar2(v,n,x));
  }
return 0;
}

int binar0(int v[], int n, int x)
{
 int l,r,m;
 l=1,r=n; //stabilim capetele vectorului
 
 while(l<=r) //cat timp putem cauta in vector
 {
  m=(l+r)/2; //mislocul portiunii v[l] - v[r]
  if(v[m]==x)
   return m; //am gasit elementul, deci returnam pozitia
  if(v[m]>x)
   r=m-1; //elementul gasit la pozitia m este mai mare dacat x, deci restrictionam cautarea in prima jumatate
  else l=m+1; //elementul gasit la pozitia m este mai mic decat x, deci restrictionam cautarea in a 2-a jumatate
 }
 return -1; //nu a fost gasit elementul
}

int binar1(int v[], int n, int x)
{
 int l,r,m,poz=-1;
 l=1,r=n; //stabilim capetele vectorului
 
 while(l<=r)
 {
  m=(l+r)/2; //mislocul portiunii v[i] - v[r]
  if(v[m]<=x) //mm gasit un numar mai mic sau egal decat x
  {
   poz=m; //salvam pozitia lui
   l=m+1; //cautam in continuare in partea dreapta un numar mai mare decat v[m] si mai mic sau egal decat x
  }
  else r=m-1; //numarul este mai mare, deci cautam in partea stanga
 }
 return poz;
}
	
int binar2(int v[], int n, int x)
{
 int l,r,m,poz=-1;
 l=1,r=n; //stabilim capetele vectorului
 
 while(l<=r)
 {
  m=(l+r)/2; //mislocul portiunii v[i] - v[r]
  if(v[m]>=x) //am gasit un numar mai mare sau egal cu x
  {
   poz=m; //salvam pozitia lui
   r=m-1; //cautam in continuare in partea stanga un numar mai mic decat v[m] si mai mare sau egal decat x
  }
  else
   l=m+1; //numarul este mai mic, deci cautam in partea dreapta
 }
 return poz;
}