#include<fstream>
using namespace std;
long int a[100005],n,m,i,j,x,y;

long cautbin0(long x,long st,long dr)
{
    long p=-1,mij;
    p=-1;
    st=1;dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x){p=mij; st=mij+1;}
        else if(x>a[mij]) st=mij+1;
             else dr=mij-1;
    }
    return p;
}

 long cautbin1(long x,long st,long dr)
{
    long p=-1,mij;
    p=-1;
    st=1;dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x){p=mij; st=mij+1;}
        else  dr=mij-1;
    }
    return p;
}

long cautbin2(long x,long st,long dr)
{
    long p=-1,mij;
    p=n+1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x){p=mij; dr=mij-1;}
        else st=mij+1;
    }
    return p;
}

int main ()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
    }
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>y>>x;
        if(y==0) g<<cautbin0(x,1,n)<<endl;
        else if(y==1) g<<cautbin1(x,1,n)<<"\n";
        else g<<cautbin2(x,1,n)<<"\n";
    }
    return 0;
}