#include <iostream>
#include<fstream>

using namespace std;

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

int pozitie;

int cautbin( int inc,  int sf, int v[], int b)
{
 int mij=(inc+sf)/2;
 if(mij==inc&&mij==sf&&v[mij]!=b)
    return -1;
    if(b==v[mij])
        return mij;
    else
        if(b>v[mij])
            return cautbin(mij+1,sf,v,b);
            return cautbin(inc,mij,v,b);
}

int cautbin1( int inc,  int sf, int v[], int b)
{
    int mij;
    while(inc<=sf)
    {
        mij=(sf+inc)/2;
        if(v[mij]>=b)
            inc++;
        else
            sf--;
    }
    mij=(inc+sf)/2;
    if(v[mij]>b)
        mij--;
    return mij;
}
int cautbin2( int inc,  int sf, int v[], int b)
{


int mij;
    while(inc<=sf)
    {
        mij=(sf+inc)/2;
        if(v[mij]<=b)
            inc++;
        else
            sf--;
    }
    mij=(inc+sf)/2;
    if(v[mij]>b)
        mij--;
    return mij;

}
int main()
{
     int v[100000],i,j,n,mij,m;

    f>>n;
    for(int i=0;i<n;i++)
        f>>v[i];

    f>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        f>>a>>b;
            if(a==0)
                {
                pozitie=cautbin(0,n-1,v,b);
                while(b==v[pozitie]&&pozitie<n)
                    pozitie++;
                    g<<pozitie<<'\n';


                }
                else if (a==1)
                {
                    pozitie=cautbin1(0,n-1,v,b);
                while(b>=v[pozitie]&&pozitie<n)
                    pozitie++;
                                       g<<pozitie<<'\n';

                }
                else
                {
                    pozitie=cautbin2(0,n-1,v,b);
                                    while(b<=v[pozitie]&&pozitie>0)
                                        pozitie--;
                                    pozitie+=2;

                    g<<pozitie<<'\n';
                }


    }


    return 0;
}