#include<stdio.h>
long n,i,a[100005],m,x,nr,st,dr,k,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",&m);
 for(i=1;i<=m;++i)
    {scanf("%ld%ld",&x,&nr);
     st=1;
     dr=n;
     if(x!=1)
     {while(st<=dr)
       {mm=(st+dr)/2;
        if(nr<a[mm])dr=mm-1;
             else st=mm+1;}
      k=dr;
      if(x==2&&a[k]!=nr)++k;
      if(a[k]!=nr&&x==0)printf("-1\n");
                   else printf("%ld\n",k);
     }
      else
    {while(st<=dr)
       {mm=(st+dr)/2;
        if(nr<=a[mm])dr=mm-1;
             else st=mm+1;}
      k=st;
      if(a[k]!=nr)--k;
      printf("%ld\n",k);
     }
    }
 return 0;
}