#include<fstream>

using namespace std;

int v[100000],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)  {mijl++;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(x<v[mijl])  j=mijl-1;
      else         i=mijl+1;
    } 
 mijl=(i+j)/2;  
 if(v[mijl]>x)  mijl--;
 mijl++;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])   mijl++;
 mijl++;return mijl;  
}  
                 
int main()
{int m,i,x,tip;
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
 f>>n;
 for(i=0;i<n;i++)
   f>>v[i];
 f>>m;  
 for(i=1;i<=m;i++)
   {f>>tip;
    f>>x;
    if(tip==0)  g<<c0(x,0,n-1)<<"\n";
    else 
      if(tip==1)  g<<c1(x,0,n-1)<<"\n";
        else      g<<c2(x,0,n-1)<<"\n";
    }   
 f.close();
 g.close();
 return 0; 
}