#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,a[100001],m,c,nr,st,dr,poz,x;
int cautare0(int x)
{
    int lo=1,hi=n,mi;
    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        if(a[mi]>x)
            lo=mi+1;
        else
            hi=mi-1;
    }
    g<<hi<<'\n';
}
void cautare1(int x)
{
    int lo=1,hi=n,mi;
    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        if(a[mi]<=x)
            lo=mi;
        else
            hi=mi;
    }
    g<<lo<<'\n';

}
void cautare2(int x)
{
    int lo=1,hi=n,mi;
    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        if(a[mi]==x)
        {
            g<<mi<<'\n';
            return;
        }
        if(a[mi]<=x)
            hi=mi-1;
        else
            lo=mi;
    }
    g<<lo<<'\n';
}

int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>a[i];
    f>>m;
    for(int i=1; i<=m; i++)
    {
        f>>c>>nr;
        if(!c)
            cautare0(nr);
        else if(c==1)
            cautare1(nr);
        else
            cautare2(nr);
    }
    return 0;
}