#include <fstream>

using namespace std;

int N,M,i,A[100001],C,X;

int binar0(int X)
{
    int St,Dr,Mij;

    St=1;
    Dr=N;
    while(St<=Dr)
    {
        Mij=(St+Dr)/2;
        if(A[Mij]<=X)
            St=Mij+1;
        else
            Dr=Mij-1;
    }//while
    Mij=(St+Dr)/2;
    if(A[Mij]>X)
        Mij--;
    if(A[Mij]==X)
        return Mij;
    return -1;
}

int binar1(int X)
{
    int St,Dr,Mij;

    St=1;
    Dr=N;
    while(St<Dr)
    {
        Mij=(St+Dr)/2;
        if(A[Mij]<=X)
            St=Mij+1;
        else
            Dr=Mij;
    }//while
    if(A[Mij]>X)
        Mij--;
    return Mij;
}

int binar2(int X)
{
    int St,Dr,Mij;

    St=1;
    Dr=N;
    while(St<Dr)
    {
        Mij=(St+Dr)/2;
        if(A[Mij]<X)
            St=Mij+1;
        else
            Dr=Mij;
    }//while
    if(A[Mij]<X)
        Mij++;
    return Mij;
}
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    fin>>N;
    for(i=1;i<=N;i++)
        fin>>A[i];
    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>C>>X;
        if(C==0)
            fout<<binar0(X);
        else
            if(C==1)
                fout<<binar1(X);
            else
                fout<<binar2(X);
        fout<<'\n';
    }//for

    fin.close ();
    fout.close();
    return 0;
}