#include <fstream>

using namespace std;

fstream f;
fstream g;
int n;
int m;
int i;
int vect[100000];
int tip, nr;
int fl; 

int binary1(int x)
{
  int lo,hi,med;
  
  for(lo=1,hi=n;lo<=hi;)
  {
      med = lo+(lo-hi)/2;
      if(x<vect[med]) hi = med-1;
      else if(x> vect[med]) lo = med+1;
      else return med;                      
  }     
  return -1;
}
     
int binary2(int x)
{
      int lo,hi,med,last=-1;
  
  for(lo=1,hi=n;lo<=hi;)
  {
      med = lo+(lo-hi)/2;
      if(x<=vect[med]) last=med,lo = med+1;
      else hi=med-1;                      
  }     
  return last;
}
     
int binary3(int x)
{
      int lo,hi,med,last=n+1;
  
  for(lo=1,hi=n;lo<=hi;)
  {
      med = lo+(lo-hi)/2;
      if(x>vect[med]) last=med, hi=med-1;
      else lo=med+1;                      
  }     
  return last;
}
       
int main()
{
    f.open("cautbin.in",fstream::in);
    f >> n;
    for(i=1;i<=n;i++)
      f >> vect[i];
    f>>m;
    g.open("cautbin.out",fstream::out);
    for(i=0;i<m;i++)
    {
       f >> tip >> nr;              
       switch(tip)
       {
          case 0:
              g << binary1(nr) << "\n";
              break; 
          case 1:
               g << binary2(nr) << "\n";
              break; 
          case 2:           
               g << binary3(nr) << "\n"; 
               break;
       }               
    }
    g.close();
    return 0;
}