#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int sir[100005], n;

void bin0(int c)
{ //c - valoarea cautata
  int st=1, dr=n, m, ok=0, poz=0;
  /*while(st<=dr)
  {
     m = (int)(st+dr)/2;  
     if(sir[m]==c) 
     {
        if(m>poz)
          poz=m;
        st=m+1;
        ok=1;
     }
     else
     {
       if(sir[m]<c)
          st=m+1;
       else
          dr=m-1;
     }
  }
  if(!ok) 
     g << -1 << "\n";
  else
     g << poz << "\n";
  */
  while(st<=dr)
  {
     m=(int)(st+dr)/2;
     if(sir[m]<=c)
        st=m+1;
     else
        dr=m-1;
  }
  m=(int)(st+dr)/2;
  if(sir[m]>c) m--;
  if(sir[m]==c) g << m << "\n";
  else g << -1 << "\n";
}

void bin1(int c)
{
  //cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir
  int st=1, dr=n, m, poz=1;
  /*
  while(st<=dr)
  {
     m=(int)(st+dr)/2;
     if(sir[m]==c)
     {
        if(m>poz)
           poz=m;
        st=m+1;
     }
     else
        if(sir[m]>c)
           dr=m-1;
  }
  g << poz << "\n";
  */
  while(st<dr)
  {
     m=(int)(st+dr)/2;
     if(sir[m]<=c)
        st=m+1;
     else
        dr=m-1;
  }
  m=(int)(st+dr)/2;
  if(sir[m]>c) m--;
  g << m << "\n";
}



void bin2(int c)
{
  //cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir
  int st=1, dr=n, m, poz=n;
  /*
  while(st<=dr)
  {
     m=(int)(st+dr)/2;
     if(sir[m]==c)
     {
        if(m<poz)
           poz=m;
        dr=m-1;
     }
     else
        if(sir[m]<c)
           st=m+1;
  }
  g << poz << "\n";
  */
  while(st<dr)
  {
     m=(int)(st+dr)/2;
     if(sir[m]>=c)
        dr=m-1;
     else
        st=m+1;
  }
  m=(int)(st+dr)/2;
  if(sir[m]<c) m--;
  g << m << "\n";
}

int main()
{
    int i, j, m;
    f >> n;
    for(i=1; i<=n; i++) f >> sir[i];
    f >> m;
    for(; m>0; m--)
    {
       f >> i >> j;
       if(i==0) bin0(j);
       if(i==1) bin1(j);
       if(i==2) bin2(j);
    }
    return 0;
}