//cautare binara
#include<iostream.h>
#include<fstream>
using namespace std;
int v[36000];
 
int casee0(int st,int dr,int x)
{  int mij;
   while(st<=dr)
     {mij=(st+dr)/2;
      if(v[mij]<=x) 
         st=mij+1;
           else 
         dr=mij-1;
      }
   mij=(st+dr)/2;
   if(v[mij]>x) 
     mij--;
   if(v[mij]==x) 
    return mij;
      else 
    return -1;
}
   
int casee1(int st, int dr, int x)
{ int mij;
   while(st<dr)
    {mij=(st+dr)/2;
     if(v[mij]<=x)  
       st=mij+1;       
         else 
       dr=mij;
     }
  mij=(st+dr)/2;
  if(v[mij]>x) 
    mij--;
 return mij;
}
    
int casee2(int st, int dr, int x)
{ int mij;
  while(st<dr)
  {mij=(st+dr)/2;
   if(v[mij]<x) 
     st=mij+1;
       else 
     dr=mij; 
   }
  mij=(st+dr)/2;
  if(v[mij]<x) 
    mij++;
 return mij; 
 }
 
int main()
{ int i,n, m, optiune, x;
fstream f,g;
f.open("cautbin.in",ios::in);
g.open("cautbin.out",ios::out);
f>>n;
for(i=1;i<=n;i++)
  f>>v[i];
f>>m;
for(i=1;i<=m;i++)
{
 f>>optiune>>x;
 if(optiune==0) g<<casee0(1,n,x)<<"\n";
 if(optiune==1) g<<casee1(1,n,x)<<"\n";
 if(optiune==2) g<<casee2(1,n,x)<<"\n";
}
f.close();
g.close();
return 0;
}