#include<stdio.h>
int x,a[140001],i,j,n,st,dr,nr,q,t;
int cauta(int st1 ,int dr1)
{ int  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("%d",&n);
  for(i=1;i<=n;i++)
   scanf("%d",&a[i]);
  scanf("%d",&t);
  for(i=1;i<=t;i++)
  { if(i==1074) x=nr;
    scanf("%d%d",&q,&nr);
     dr=n;
    int u=cauta(1,dr);
    if(a[u]==nr)
      printf("%d\n",u);

    else
    {
    if(q==0) printf("-1\n");
     if(q==1)
      printf("%d\n",u-1);
    if(q==2)
      printf("%d\n",u);

      }
      }
return 0;}