#include <fstream>
using namespace std;

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

int a[100005],m,n,x,y;

int caz0(int b)
{
    int li=1,ls=n,mij,fin=-1;
    while(li<=ls)
    {
        mij=(li+ls)/2;
        if (a[mij]==b)
        {
            fin=mij;
            li=mij+1;
        }
        if(a[mij]<b)
            li=mij+1;
        if (a[mij]>b)
            ls=mij-1;
    }
        return fin;
}

int caz1(int b)
{
    int li=1, ls=n, mij, fin;
    while( li<=ls)
    {
        mij=(li+ls)/2;
        if (a[mij]<=b)
        {
            fin=mij;
            li=mij+1;
        }
        else
            ls=mij-1;
    }
    return fin;
}

int caz2(int b)
{
    int li=1,ls=n,mij,fin;
    while(li<=ls)
    {
    mij=(li+ls)/2;
    if (a[mij]>=b)
    {
        fin=mij;
        ls=mij-1;
    }
    else
    li=mij+1;
    }
    return fin;
}
int main()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
        for(i=1;i<=m;i++)
        {
            f>>x>>y;
            if(x==0) g<<caz0(y)<<"\n";
            if(x==1) g<<caz1(y)<<"\n";
            if (x==2) g<<caz2(y)<<"\n";
        }
    return 0;
}