#include <iostream>
#include <fstream>
 
using namespace std;
 
int v[100001], N, M, mij, x, nr;
 
int caut_bin0(int k, int inf, int sup)
{
      while (inf<=sup)
            {mij=inf+(sup-inf)/2;
             if (v[mij]<=k)
                 inf=mij+1;
             else    
                 sup=mij-1;}
      mij=inf+(sup-inf)/2;
      if (v[mij]>k) mij--;
      if (v[mij]==k) return mij;
      else return -1;                              
}
 
int caut_bin1 (int k, int inf, int sup)
{
        while (inf<sup)
              {mij=inf+(sup-inf)/2;
               if (v[mij]<=k)
                   inf=mij+1;
                else 
                   sup=mij;}
        mij=inf+(sup-inf)/2;
        if (v[mij]>k) mij--;
        return mij;                                       
}
 
int caut_bin2 (int k, int inf, int sup)
{
        while (inf<sup)
              {mij=inf+(sup-inf)/2;
               if (v[mij]<k)
                   inf==mij+1;
               else 
                   sup=mij;}   
        mij=inf+(sup-inf)/2;
        if (v[mij]<k) mij++;
        return mij;                                                
}  
 
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 i=1; i<=M; i++)
          {f>>nr>>x;
           if (nr==0)       
               g<<caut_bin0(x,1,N);     
           if (nr==1)     
               g<<caut_bin1(x,1,N);
           if (nr==2)    
               g<<caut_bin2(x,1,N);}
      f.close();
      g.close();         
      return 0;        
}