#include<fstream.h>
int a[100001],n;
int bin1(int y)
{
 int lo,hi,mid;
  for (lo = 1, hi = n; lo <= hi; )
    {   
        mid = lo + (hi-lo) / 2;   
        if (y < a[mid]) hi = mid-1;   
        else if (a[mid] < y) lo = mid+1;   
        else return mid;   
    }   
    return -1;
 }
int bin2(int y)
{
    int lo, hi, mid, last = 0;   
  
    for (lo = 1, hi = n; lo <= hi; )   
    {   
        mid = lo + (hi-lo) / 2;   
        if (a[mid] <= y) last = mid, lo = mid+1;   
        else hi = mid-1;   
    }   
    return last;   
}
int bin3(int y)
{
    int lo, hi, mid, last = n+1;   
  
    for (lo = 1, hi = n; lo <= hi; )   
    {   
        mid = lo + (hi-lo) / 2;   
        if (y <= a[mid]) last = mid, hi = mid-1;   
        else lo = mid+1;   
    }   
    return last;   
}
int main()
{
int x,y,m,i;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
f>>m;
for(i=1;i<=m;i++)
 {
  f>>x>>y;
  if(x==0)
    g<<bin1(y)<<"\n";
   else
    if(x==1)
      g<<bin2(y)<<"\n";
    else
      g<<bin3(y)<<"\n";
  }
  return 0;
}