#include <stdio.h>
#define MAX 100001
int  a[MAX], n;
int q(int x, int op)
{
 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;
 if(op==1) return -dr;
 else if(op==2) return -st;
 else return -1;
// return op==0?-1:op==1?-st:-dr;
}

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);


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