#include<stdio.h>
#define NM 100005
int v[NM],N;
int caut0(int x)
{
  int p=0,u=N-1,m,pok=-1;
  while (p<=u)
  {
    m=(p+u)>>1;
    if (x<=v[m])
    {
      pok=m;
      p=m+1;
    }
    else
      u=m-1;
  }
  if (x==v[pok])
  return pok+1;
  return -1;
}
int cauta1(int x)
{
  int p=0,u=N-1,m,pok=-2;
  while (p<=u)
  {
    m=(p+u)>>1;
    if (x<=v[m])
    {
      pok=m;
      p=m+1;
    }
    else
      u=m-1;
  }
  return pok+1;
}
int cauta2(int x)
{
  int p=0,u=N-1,m,pok=-2;
  while (p<=u)
  {
    m=(p+u)>>1;
    if (x>=v[m])
    {
      pok=m;
      u=m-1;
    }
    else
      p=m+1;
  }
  return pok+1;
}
int main()
{
  freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);
  scanf("%d",&N);
  int x,op;
  for (int i=N-1; i>=0; --i)
    scanf("%d",&v[i]);
  int g;
  scanf("%d",&g);
  while (g--)
  {
    scanf("%d%d",&op,&x);
    if (op==0)
    {

        printf("%d\n",caut0(x));
      continue;
    }
    if (op==1)
    {
      printf("%d\n",cauta1(x));
      continue;
    }
    printf("%d\n",cauta2(x));
  }
  return 0;
}