#include<stdio.h>
int x,a[140001],i,j,n,st,max,dr,nr,q,t,m;
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]);
  if(max<a[i]) max=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)
      { while(a[u]==a[u-1]&&u<=n&&u>0)
         u--;
      printf("%d\n",u-1);  }
    if(q==2)
     { while(a[u]==a[u+1]&&u>0&&u<=n)
         u++;
     printf("%d\n",u);
      }
      }
      }
return 0;}