#include <fstream>

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

int v[100002],n,m,i,p,a,x;
void caut0(int val)
{
    int s=1,d=n;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=val)
            s=m+1;
        else
            d=m-1;
    }
    m=(s+d)/2;
    if(v[m]>val)
        m--;
    if(v[m]==val)
        g<<m<<'\n';
    else
        g<<-1<<'\n';
}
void caut1(int val)
{
    int s=1,d=n;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=val)
            s=m+1;
        else
            d=m-1;
    }
    m=(s+d)/2;
    if(v[m]<=val)
    g<<m<<'\n';
    else
    g<<m-1<<'\n';
}
void caut2(int val)
{
    int s=1,d=n;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<val)
            s=m+1;
        else
            d=m-1;
    }
    m=(s+d)/2;
    if(v[m]>=val)
        g<<m<<'\n';
    else
        g<<m+1<<'\n';
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>p;
    for(i=1;i<=p;i++)
    {
        f>>a>>x;
        if(a==0)
            caut0(x);
        if(a==1)
            caut1(x);
        if(a==2)
            caut2(x);
    }

    return 0;
}