#include <fstream>

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

int N,M,i,st,dr,mij,pozMax;
unsigned int a[100001],q;
unsigned p;

int main()
{
    f>>N;
    for(i=1;i<=N;i++)
        f>>a[i];

    f>>M;
    for(i=1;i<=M;i++){
        f>>p>>q;

        if(p==0){
            st=1,dr=N,pozMax=0;
            while(st<dr){

                mij=(st+dr)/2;
                if(a[mij]==q){

                    pozMax=max(pozMax,mij);
                    if(q>=a[mij])st=mij+1;

                }else if(q>=a[mij])st=mij+1;
                else if(q<=a[mij])dr=mij-1;

            }

            g<<pozMax<<"\n";

        }else if(p==1){

            st=1,dr=N;
            while(st<dr){
                mij=(st+dr)/2;

            if(a[mij]>q)dr=mij;
            else st=mij+1;

            }

            mij=(dr+st)/2;
            if(a[mij]>q)
                mij--;

            g<<mij<<"\n";

        }else if(p==2){

            st=1,dr=N;
            while(st<dr){
                mij=(st+dr)/2;

                if(a[mij]<q)
                    st=mij+1;
                else
                    dr=mij;

            }

            mij=(st+dr)/2;
            if(a[mij]<q)
                ++ mij;

            g<<mij<<"\n";

        }

    }

}