#include<stdio.h>
long n,i,a[100100],x,y,st,dr,m,mm;
int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)
    scanf("%ld",&a[i]);
 scanf("%ld",&mm);
 for(i=1;i<=mm;++i)
    {scanf("%ld%ld",&x,&y);
     st=1;dr=n;
     while(st<=dr)
      {m=(st+dr)/2;
       if(x!=1)
         if(a[m]<y)st=m+1;
         else dr=m-1;
       else
         if(a[m]>y)dr=m-1;
         else st=m+1;}
     if(!x)
       if(a[st]==y)printf("%ld\n",st);
       else printf("-1\n");
     else
     if(x==1)
       if(a[dr]<=y)printf("%ld\n",dr);
       else printf("%ld\n",dr-1);
     else
     if(x==2)
       if(a[st]>=y)printf("%ld\n",st);
       else printf("%ld\n",st+1);}
 return 0;
}