#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100001],c,x,p,n,ok,st,dr,m,posib;
int cautbin0(int x)
{
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x==v[m])
        {
            ok=1;
            return m;
        }
        else
        {
            if(x<v[m])
                dr=m-1;
            else
                st=m+1;
        }
    }
    if(ok==0)
        return -1;
}
int cautbin1(int x)
{
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x==v[m] || v[m]<=x)
        {
            ok=1;
            p=m;
            st++;
            // break;
        }
        else
        {
            if(x<v[m])
                dr=m-1;
            else
                st=m+1;
        }
    }
    if(ok==0)
        return -1;
    else
        return p;
}
int cautbin2(int x)
{
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x==v[m] || v[m]>=x)
        {
            ok=1;
            p=m;
            dr--;
            // break;
            }
        else
        {
            if(x<v[m])
                dr=m-1;
            else
                st=m+1;
        }
    }
    if(ok==0)
        return -1;
    else
        return p;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    f>>posib;
    for(int i=1;i<=posib;i++)
    {
        f>>c>>x;
        st=1;dr=n;
        ok=0;
        if(c==0)
            g<<cautbin0(x)<<'\n';
        else
            if(c==1)
                g<<cautbin1(x)<<'\n';
            else
                g<<cautbin2(x)<<'\n';
    }
    return 0;
}