#include <iostream>
#include <fstream>
 
using namespace std;
 
int v[100001], N, M, mij, x, nr;
 
int caut_bin0(int k)
{
      int inf=1;
      int sup=N;    
      int p=-1;
      while (inf<=sup)
            {mij=inf+(sup-inf)/2;
             if (v[mij]==k)
                {p=mij;
                 inf=mij+1;}
             else    
                 if (v[mij]<k)
                     inf=mij+1;
                 else
                     sup=mij-1;}
      return p;                              
}
 
int caut_bin1 (int k)
{
        int inf=1;
        int sup=N;
        int p=0;
        while (inf<=sup)
              {mij=inf+(sup-inf)/2;
               if (v[mij]<=k)
                  {p=mij;
                   inf=mij+1;}
                else 
                   sup=mij-1;}
        return p;                                       
}
 
int caut_bin2 (int k)
{
        int inf=1;
        int sup=N;
        int p=0;
        while (inf<=sup)
              {mij=inf+(sup-inf)/2;
               if (v[mij]>=k)
                  {p=mij;
                   sup=mij-1;}
               else 
                   inf=mij+1;}   
        return p;                                                
}  
 
int main()
{
      ifstream f("cautbin.in");
      ofstream g("cautbin.out");
      f>>N;
      for (int i=1; i<=N; i++)
      f>>v[i];
      f>>M;
      for (int j=0; j<M; j++)
          {f>>nr>>x;
           if (nr==0)       
               g<<caut_bin0(x);     
           if (nr==1)     
               g<<caut_bin1(x);
           if (nr==2)    
               g<<caut_bin2(x);}
      f.close();
      g.close();         
      return 0;        
}