#include <fstream>

using namespace std;

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

int binary(int ll,int hl,int x,int fl)
{
     int med;
     if(fl==0)
     while(ll<hl)
     {
           med=ll+(ll+hl)/2;
           if(vect[med]==x)
             return med;
                if(vect[med]>x)
              return binary(ll,med-1,x,fl);
           else          
              return binary(med+1,hl,x,fl);
     }
     if(fl==1||fl==2)
        while(ll<hl)
     {
           med=ll+(ll+hl)/2;
           if(vect[med]==x)
             return med;
          else{
           if(fl==1)
           {
              if(vect[med-1]<x&&vect[med]>x&&med>1) return med-1;     
           }
           if(fl==2)
           {
              if(vect[med]>x&&vect[med-1]<x&& med>1) return med;         
           }
           }
          if(vect[med]>x)
              return binary(ll,med-1,x,fl);
           else          
              return binary(med+1,hl,x,fl);
     }
          
   return -1;
}
     
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 << binary(1,n,nr,0) << "\n";
              break; 
          case 1:
               g << binary(1,n,nr,1) << "\n";
              break; 
          case 2:           
               g << binary(1,n,nr,2) << "\n"; 
               break;
       }               
    }
    g.close();
    return 0;
}