#include<fstream>

using namespace std;

int v[100001],n;

int c0(int x,int i,int j)
{int mijl;
 while(i<=j)
  {mijl=(i+j)/2;
   if(x==v[mijl]) 
     if(v[mijl+1]>x)  return mijl;
   if(x<v[mijl])  j=mijl-1;
     else         i=mijl+1;  
    }   
 return -1;     
}
 
int c1(int x,int i,int j)
{int mijl;
 while(i<=j)
   {mijl=(i+j)/2;
    /*if(mijl==n && v[mijl]<=x)  return mijl;
    if(v[mijl]<=x && v[mijl+1]>x)  return mijl;
    if(v[mijl]==x)  break;
    if(mijl==n-1)
      {if(v[mijl]<x && v[n]>x)  return mijl;
         else  return n;
       }  
    if(mijl==1)
      if(v[2]>x)  return v[1];
        else      return v[2];*/
    if(x<v[mijl])  j=mijl-1;
      else         i=mijl+1;
    } 
 mijl=(i+j)/2;   
 return mijl;   
 /*if(v[mijl]==x)   
   {while(v[mijl]==x)  mijl++;  
    return (mijl-1);
    }*/   
} 
  
int c2(int x,int i,int j)
{int mijl;
 while(i<=j)
   {mijl=(i+j)/2;
    /*if(mijl==1)
      {if(v[mijl]>=x)  return mijl;
         else          return 2;
       }  
    if(v[mijl]>=x && v[mijl-1]<x)  return mijl;*/
    if(x<=v[mijl])  j=mijl-1; 
        else        i=mijl+1;
     }    
 mijl=(i+j)/2;
 if(x>v[mijl])   mijl++;
 return mijl;  
}  
                 
int main()
{int m,i,x,tip;
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
 f>>n;
 for(i=1;i<=n;i++)
   f>>v[i];
 f>>m;  
 for(i=1;i<=m;i++)
   {f>>tip;
    f>>x;
    if(tip==0)  g<<c0(x,1,n)<<endl;
    else 
      if(tip==1)  g<<c1(x,1,n)<<endl;
        else      g<<c2(x,1,n)<<endl;
    }   
 f.close();
 g.close();
 return 0; 
}