/// Craciun Catalin
///  Cautbin
///   www.infoarena.ro/problema/cautbin
#include <fstream>
#include <iostream>

#define NMax 100005

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

long V[NMax];
long n,m;

long cautBin1(long el)
{
    long st=1, dr=n;
    long poz;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<=el)
        {
            st=m+1;
            poz=st;
        }
        else
            dr=m-1;
    }

    long m=(st+dr)/2;

    if (V[m]>el)
        return m-1;
    else if (V[m]==el)
        return m;
    else
        return 0;
}

long cautBin2(long el)
{
    long st=1, dr=n;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<=el)
        {
            st=m+1;
            poz=st;
        }
        else
            dr=m-1;
    }

    while (V[m]>el)
        m--;

    return m;
}

long cautBin3(long el)
{
    long st=1, dr=n;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<el)
            st=m+1;
        else
            dr=m-1;
    }

    long m=(st+dr)/2;

    while (V[m]<el)
        m++;

    return m;
}

int main()
{
    f>>n;
    for (long i=1;i<=n;i++)
        f>>V[i];
    f>>m;
    for (long i=1;i<=m;i++)
    {
        long x,y;
        f>>x>>y;
        if (x==0)
            g<<cautBin1(y)<<'\n';
        else if (x==1)
            g<<cautBin2(y)<<'\n';
        else if (x==2)
            g<<cautBin3(y)<<'\n';
    }
    f.close();

    return 0;
}