#include <iostream>
#include <fstream>

using namespace std;

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

int v[100005], n, i, t, cer, x, p;

int cautbin1(int st, int dr, int elem)
{
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] <= elem)
        {
            p = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return p;
}

int cautbin2(int st, int dr, int elem)
{
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] <= x) st = mij + 1;
        else dr = mij - 1;
    }
    return dr;
}

int cautbin3(int st, int dr, int elem)
{
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] >= x) dr = mij - 1;
        else st = mij + 1;
    }
    return st;
}

int main()
{
    f >> n;

    for(i=1; i<=n; ++i)
    {
        f>>v[i];
    }
    f>>t;
    while(t--)
    {
        f>>cer>>x;
        if(cer==0) g<<cautbin1(1,n,x)<<"\n";
        else if(cer==1) g<<cautbin2(1,n,x)<<"\n";
        else g<<cautbin3(1,n,x)<<"\n";
    }
    return 0;
}