#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,k,v[100005],val, cerinta;
void citire();
int  last_poz(int);
int  lower_boun(int);
int  upper_boun(int );

int main()
{
    citire();
    return 0;
}
void citire()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>v[i];
    fin>>k;
    for(int i=1;i<=k;i++) {fin>>cerinta>>val;
    if(cerinta==0)
        fout<<last_poz(val)<<'\n';
    else if(cerinta==1) fout<<lower_boun(val)<<'\n';
    else fout<<upper_boun(val)<<'\n';
    }

}
int  lower_boun(int x)
{
    int inc=0,sf=n+1,mij;
    while(sf-inc>1)
    {
        mij=(sf+inc)/2;
        if(v[mij]<=x)
            inc=mij;
        else
            sf=mij;
    }
    return inc;
}
int  upper_boun(int x)
{
    int inc=0,sf=n+1,mij;
    while(sf-inc>1)
    {
        mij=(sf+inc)/2;
        if(v[mij]<x)
            inc=mij;
        else
            sf=mij;
    }
    return sf;
}

int  last_poz(int x)
{
    int inc=0,sf=n+1,mij;
    while(sf-inc>1)
    {
        mij=(sf+inc)/2;
        if(v[mij]<=x)
            inc=mij;
        else
            sf=mij;
    }
    if(v[inc]==x) return inc; else return -1;
}