#include <stdio.h>
#define MAX 100001
int  a[MAX], n;
int q(int x)
{
 int st=1, dr=n;
 while(st<dr)
  if(a[(st+dr)/2]>x) st=(st+dr)/2+1;
   else if(a[(st+dr)/2]<x) dr=(st+dr)/2-1;
    else return (st+dr)/2;
 return -1;
}

int main()
{
 int i, m, op, el, v;
 int st, dr;
 FILE *fi=fopen("cautbin.in", "r"), *fo=fopen("cautbin.out", "w");
 fscanf(fi, "%d", &n);
 for(i=1; i<=n; i++)
  fscanf(fi, "%d", &a[i]);
 fscanf(fi, "%d", &m);
 for(i=1; i<=m; i++)
  {
   fscanf(fi, "%d%d", &op, &el);
   v=q(el);

   if(op==0)
   {
    fprintf(fo, "%d\n", v);
   }
   else
   if(op==1)
   {
    if(v>0)
    {
     fprintf(fo, "%d\n", v-1);
    }
    else
    {
     st=1; dr=n;
     if(a[(st+dr)/2]>el)
     {
      while(a[(st+dr)/2]>el) dr=(st+dr)/2-1;
      for(; a[dr]<el; dr++);
      fprintf(fo, "%d\n", dr);
     }
     else
     if(a[(st+dr)/2]<el)
     {
      while(a[(st+dr)/2]<el) st=(st+dr)/2+1;
      for(; a[st]>el; st--);
      fprintf(fo, "%d\n", st);
     }
    }
   }
   else
   {
    if(v>0)
    {
     fprintf(fo, "%d\n", v+1);
    }
    else
    {
     st=1; dr=n;
     if(a[(st+dr)/2]>el)
     {
      while(a[(st+dr)/2]>el) dr=(st+dr)/2-1;
      for(; a[dr]<el; dr++);
      fprintf(fo, "%d\n", dr);
     }
     else
     if(a[(st+dr)/2]<el)
     {
      while(a[(st+dr)/2]<el) st=(st+dr)/2+1;
      for(; a[st]>el; st--);
      fprintf(fo, "%d\n", st+1);
     }
    }
   }
  }
 fclose(fi);
 fclose(fo);
 return 0;
}