#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;
}