/// arta tata


#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int st,dr,mij,x,n,a;

int caut1()
{
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    if(v[dr]==x)
        return dr;
    else
        return -1;
}
int caut2()
{
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
        return dr;
}
int caut3()
{
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
            dr=mij-1;
        else
            st=mij+1;
    }
        return st;
}
int pety()
{
    int m,z;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
        fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>z>>x;
        if(z==0)
            fout<<caut1()<<'\n';
        if(z==1)
            fout<<caut2()<<'\n';
        if(z==2)
            fout<<caut3()<<'\n';
    }
    return 0;
}