#include<stdio.h>
int a[100001],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++)
  { 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;}