#include <iostream>
#include <fstream>

using namespace std;

int n, a[100000];

int cautbin1 (int x)
{
    int step, i;
    for (step=1;step<n;step <<= 1);
    for (i=0;step;step >>= 1)
        if (step+i<=n&&a[step+i]<=x)
            i+=step;
    return i;
}

int cautbin2 (int x)
{
    int step, i;
    for (step=1;step<n;step <<= 1);
    for (i=n;step;step >>= 1)
        if (i-step<=n&&a[i-step]>=x)
            i-=step;
    return i;
}

int main()
{
    int m, c, val;
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>c>>val;
        if (c==0||c==1)
            fout<<cautbin1(val)<<"\n";
        else
            fout<<cautbin2(val)<<"\n";
    }
    return 0;
}