#include <stdio.h>
#include <stdlib.h>
int n,m,a[100001],op,x,poz;
int Cautbin(int opp,int nr)
{ if(opp==0)
     { int st=1,dr=n,mij;
         while(st<=dr)
          { mij=st+(dr-st)/2;
             if(a[mij]==nr&&a[mij+1]!=nr) {return mij;}
             else if(a[mij]==nr&&a[mij+1]==nr) {st=mij+1;}
             else  if(a[mij]<nr) {st=mij+1;}
             else  if(a[mij]>nr) {dr=mij-1;}
          }
          return -1;
     }
  else if(opp==1)
  { int st=1,dr=n,mij;
         while(st<=dr)
          { mij=st+(dr-st)/2;
             if(a[mij]==nr&&a[mij+1]!=nr) {return mij;}
             else if(a[mij]==nr&&a[mij+1]==nr) {st=mij+1;}
             else  if(a[mij]<nr) {st=mij+1;}
             else  if(a[mij]>nr) {dr=mij-1;}
          }
         if(a[mij]<nr) return mij;
         if(a[mij]>nr) return mij-1;
   }
   else if(opp==2)
  { int st=1,dr=n,mij;
         while(st<=dr)
          { mij=st+(dr-st)/2;
             if(a[mij]==nr&&a[mij-1]!=nr) {return mij;}
             else if(a[mij]==nr&&a[mij-1]==nr) {dr=mij-1;}
             else  if(a[mij]<nr) {st=mij+1;}
             else  if(a[mij]>nr) {dr=mij-1;}
          }
         if(a[mij]<nr) return mij+1;
         if(a[mij]>nr) return mij;
   }
}
int main()
{ FILE *f,*g;
  f=fopen("cautbin.in","r");
  g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    int i;
    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",&op,&x);
    poz=Cautbin(op,x);
    fprintf(g,"%d\n",poz);
    }
    return 0;
}