#include<stdio.h>
long a[40000],i,j,n,st,dr,nr,q,t;
int cauta(long st1 ,long dr1)
{ long  mij=st1+(dr1-st1)/2;
  if(a[mij]==nr) return mij;
  if(st1<=dr1)
  {if(nr<a[mij])
   return cauta(st1,mij-1);
   if(nr>a[mij])
    return cauta(mij+1,dr1);    }
  return mij;   }
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",&t);
  for(i=1;i<=t;i++)
  { scanf("%ld%ld",&q,&nr);
   dr=n;
    long u=cauta(1,dr);
    if(a[u]==nr)
      printf("%ld\n",u);
    else
    { if(q==0) printf("-1\n");
      if(q==1) printf("%ld\n",u-1);
      if(q==2) printf("%ld\n",u);
      }
      }
return 0;}