#include <stdio.h>
long sir[100001];
int main ()
{long st,dr,n,m,i,a,b,p;
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%ld",&n);
 for (i=1;i<=n;i++)
  scanf("%ld",&sir[i]);
 scanf("%ld",&m);
 for (i=1;i<=m;i++)
 {scanf("%ld%ld",&a,&b);
  switch(a)
  {case 0:
   for (st=1,dr=n;st<=dr&&!(sir[p=(st+dr)/2]==b&&((p<n&&sir[p+1]!=b)||(p==n)));)
   {if(sir[p]<b)
    {st=p+1;}
    else
    {dr=p-1;}
   }
   if(st>dr)
   {printf("-1\n");}
   else
   {printf("%ld\n",p);
   }
   break;
   case 1:
   for (st=1,dr=n;!(sir[p=(st+dr)/2]<=b&&((p<n&&sir[p+1]>b)||(p==n)));)
   {if(sir[p]<b)
    {st=p+1;}
    else
    {dr=p-1;}
   }
   printf("%ld\n",p);
   break;
   case 2:
   for (st=1,dr=n;!(sir[p=(st+dr)/2]>=b&&((p>1&&sir[p-1]<b)||(p==1)));)
   {if(sir[p]<b)
    {st=p+1;}
    else
    {dr=p-1;}
   }
   printf("%ld\n",p);
  }
  
 }
 return 0;
}