#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int m,n,i,j,a[100002],k1,k2;
int caut0()
{
    int st,dr,mij,k;
    st=1;dr=n;
    k=-1;
    while(st<=dr)
            {
                mij=(st+dr)/2;
                if(a[mij]==k2)
                {
                        k=mij;
                        st=mij+1;
                }
                else
                {
                    if(a[mij]<k2)
                    {
                        st=mij+1;
                    }
                    else
                        dr=mij-1;
                }
            }
           return k;
}
int caut1()
{
    int st=1,dr=n,mij,k=0;

                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(a[mij]<=k2)
                    {
                            k=mij;
                            st=mij+1;
                    }
                    else
                        dr=mij-1;
                }
                return k;
}
int caut2()
{
    int dr=n,st=1,k=0,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=k2)
        {
                k=mij;
                dr=mij-1;
        }
        else
            st=mij+1;
    }
    return k;
}
int main()
{

    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    fin>>m;
    for(i=1;i<=m;i++)
    {
            fin>>k1>>k2;

            if(k1==0)
                fout<<caut0()<<"\n";
            if(k1==1)
                fout<<caut1()<<"\n";

            if(k1==2)
                fout<<caut2()<<"\n";
    }
    return 0;
}