#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int elemente[100005], numar1, nr_elem, nr_intrebari, numar2;

///Aceasta functie returneaza cea mai mare pozitie pe care se gaseste un element sau -1 daca nu gasim elementul in sir;
int cautareBinara1(int numere[], int nr_elemente, int numar)
{
    int capat_stanga=1, pozitieDreapta=-1, pozitieStanga=-1;
    int capat_dreapta=nr_elemente;
    ///Am cautat numarul transmis ca parametru pe pozitia mijlocului si pe celelalte pozitii de dupa mijloc pana la final;
    while(capat_stanga<=capat_dreapta)
    {
        int mijloc=(capat_stanga+capat_dreapta)/2;
        if(numere[mijloc]<=numar)
        {
            capat_stanga=mijloc+1;
            pozitieDreapta=mijloc;
        }
        else
        {
            capat_stanga++;
        }
    }
    ///Daca nu l-am gasit in partea dreapta caut numarul in partea stanga de la pozitia 1 pana la pozitia mijlocului;
    if(pozitieDreapta==-1)
    {
        capat_stanga=1;
        capat_dreapta=nr_elemente;
        capat_dreapta=((capat_stanga+capat_dreapta)/2)-1;
        while(capat_stanga<=capat_dreapta)
        {
            int mijloc=(capat_stanga+capat_dreapta)/2;
            if(numere[mijloc]>=numar)
            {
                capat_stanga=mijloc+1;
                pozitieStanga=mijloc;
            }
            else
            {
                capat_stanga++;
            }
        }
        return pozitieStanga;
    }
    else return pozitieDreapta;
}

///Aceasta functie returneaza cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir;
int cautareBinara2(int numere[], int nr_elemente, int numar)
{
    int capat_stanga=1, pozitieStanga=-1;
    int capat_dreapta=nr_elemente;
    capat_dreapta=((capat_stanga+capat_dreapta)/2)-1;
    while(capat_stanga<=capat_dreapta)
    {
        int mijloc=(capat_stanga+capat_dreapta)/2;
        if(numere[mijloc]>=numar)
        {
            capat_dreapta=mijloc-1;
            pozitieStanga=mijloc;
        }
        else
        {
            capat_stanga++;
        }
    }
    return pozitieStanga;
}

int main()
{
    fin>>nr_elem;
    for(int i=1;i<=nr_elem;i++)
        fin>>elemente[i];
    fin>>nr_intrebari;
    for(int j=1;j<=nr_intrebari;j++)
    {
        fin>>numar1>>numar2;
        if(numar1==0)
            fout<<cautareBinara1(elemente,nr_elem,numar2)<<"\n";
        if(numar1==1)
            fout<<cautareBinara1(elemente,nr_elem,numar2)<<"\n";
        if(numar1==2)
            fout<<cautareBinara2(elemente,nr_elem,numar2)<<"\n";
    }
    return 0;
}