#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,x,i,v[100002],t,y,c,m;
int bin(int n1)
{
    int st=1,dr=n,poz=0,mij,i=0,r;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]==n1)
        {
            poz=mij;
        }

        if(v[mij]<n1)
            st=mij+1;
        else
            dr=mij-1;
    }
    while(v[poz+i]==n1)
    {
        i++;
        r=poz+i;
    }
    r--;
    return r;
}
int bin1(int n1)
{
    int mij=0,st=1,dr=n,poz=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=n1)
        {
            poz=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return poz;
}
int bin2(int n1)
{
    int mij=0,st=1,dr=n,poz=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=n1)
        {
            poz=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return poz;
}
int main()
{
   f>>n;
   for(i=1;i<=n;i++)
    f>>v[i];
f>>m;
for(i=1;i<=m;i++)
{
    f>>c>>x;
    if(c==0)
  g<<bin(x)<<'\n';
  if(c==1)
    g<<bin1(x)<<'\n';
  if(c==2)
  g<<bin2(x)<<'\n';
}




    return 0;
}