#include <fstream>

using namespace std;

long a[1000],n,m,i,x,y,lg,step;

long keres1(long mit)
{
  long st=lg,q;  
  for (q=0;st>0;st>>=1)
   if (q+st<n&&a[q+st]<=mit) q+=st;  
  
  if (a[q]==mit) return q;  
  return -1;    
}

long keres2(long mit)
{
  long st=lg,q;  
  for (q=0;st>0;st>>=1)
   if (q+st<n&&a[q+st]<=mit) q+=st;  
  
  return q;   
}

long keres3(long mit)
{
  long st=lg,q;  
  for (q=n;st>0;st>>=1)
   if (q-st>0&&a[q-st]>=mit) q-=st;  
  
  return q;  
}


int main()
{
  ifstream in("cautbin.in");
  ofstream out("cautbin.out");
  
  in >> n;
  
  for (lg=1; lg<n; lg <<= 1);
  
  for (i=1;i<=n;++i) in >> a[i];
  in >> m;
  for (i=1;i<=m;++i) 
  {
    in >> x >> y;
    if (x==0) out << keres1(y) << "\n"; else
    if (x==1) out << keres2(y) << "\n"; else
    out << keres3(y) << "\n";    
  }  
    
  in.close();
  out.close();  
    
  return 0;    
}