#include <stdio.h>

int a[100005],n,m,i,x,val;


/*int CautareBinara(int li,int ls,int val)
  {int mid=li+(ls-li)/2;
   if (a[mid]==val) {while (a[mid+1]==val)
                             mid++;
                     return mid;
                     }
             else
             if (a[mid]>val) CautareBinara(li,mid-1,val);
                        else CautareBinara(mid+1,ls,val);
   return -1;
   }*/

int CautareBinara1(int li,int ls,int val)
  {int mid;
   while (li<=ls)
      {mid=li+(ls-li)/2;
       if (a[mid]==val) {while (a[mid+1]==val)
                             mid++;
                         return mid;
                         }
                   else
             if (a[mid]>val) ls=mid-1;
                        else li=mid+1;
       }
   return -1;
   }

int CautareBinara2(int li,int ls,int val)
  {int mid;
   while (li<=ls)
     {mid=li+(ls-li)/2;
       if (a[mid]==val) return mid;
                   else
             if (a[mid]>val) ls=mid-1;
                        else li=mid+1;
       }
   return ls;
   }

int CautareBinara3(int li,int ls,int val)
  {int mid;
   while (li<=ls)
     {mid=li+(ls-li)/2;
       if (a[mid]==val) /*{while (a[mid+1]==val)
                             mid++;
                         return mid;
                         }*/
                         return mid; 
                   else
             if (a[mid]>val) ls=mid-1;
                        else li=mid+1;
       }
   return li;
   }

int main()
 {FILE *f,*g;

  f=fopen("cautbin.in","r");
  g=fopen("cautbin.out","w");

  fscanf(f,"%d",&n);
  for (i=1;i<=n;i++)
      fscanf(f,"%d",&a[i]);
  fscanf(f,"%d",&m);
  for (i=1;i<=m;i++)
      {fscanf(f,"%d %d",&x,&val);
       if (x==0) fprintf(g,"%d\n",CautareBinara1(1,n,val));
       if (x==1) fprintf(g,"%d\n",CautareBinara2(1,n,val));
       if (x==2) fprintf(g,"%d\n",CautareBinara3(1,n,val));
       }
  fclose(f);
  fclose(g);

  return 0;
  }