#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
int v[100000];
int bbsearch(int st, int dr, int val){
  int m;
  while(st<=dr){
    m=(dr+st)/2;
    if(v[m]>val)
      dr=m-1;
    else
      st=m+1;
  }
  m=(dr+st)/2;
  if(v[m]>val)
    m--;
  if(v[m]==val)
    return m;
  return -1;
}
int bbsearch1(int st, int dr, int val){
  int m;
  while(st<dr){
    m=(dr+st)/2;
    if(v[m]>val)
      dr=m;
    else
      st=m+1;
  }
  m=(dr+st)/2;
  if(v[m]>val)
    m--;
  return m;
}
int bbsearch2(int st, int dr, int val){
  int m;
  while(st<dr){
    m=(dr+st)/2;
    if(v[m]>=val)
      dr=m;
    else
      st=m+1;
  }
  m=(dr+st)/2;
  if(v[m]<val)
    m--;
  return m;
}
int main()
{
    int n,i,m,tipe,val;
    fin=fopen("cautbin.in","r");
    fout=fopen("cautbin.out","w");
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
      fscanf(fin,"%d",&v[i]);
    fscanf(fin,"%d",&m);
    for(i=0;i<m;i++){
      fscanf(fin,"%d%d",&tipe,&val);
      if(tipe==0)
        fprintf(fout,"%d\n",bbsearch(1,n,val));
      else if(tipe==1)
        fprintf(fout,"%d\n",bbsearch1(1,n,val));
      else if(tipe==2)
        fprintf(fout,"%d\n",bbsearch2(1,n,val));
    }

    return 0;
}