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