#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])
     {while(x==v[mijl])   mijl++;
      return (mijl-1);
      }
    else
     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(x<v[mijl])  j=mijl-1;
      else         i=mijl+1;
    }
 mijl=(i+j)/2;
 if(x<v[mijl])  return (mijl-1);    
 return mijl;
} 
  
int c2(int x,int i,int j)
{int mijl;
 while(i<j)
   {mijl=(i+j)/2;
    if(x<=v[mijl])  j=mijl-1; 
        else        i=mijl+1;
     }   
 mijl=(i+j)/2;    
 if(x>v[mijl])  return (mijl+1);    
 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; 
}