#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int i,j,n,x[100001],quest,m,nr,gasit,u,p,mij,poz;

int main()
{
    fin>>n;

    for(i=1;i<=n;i++)   //citire sir de numere
        fin>>x[i];

    fin>>m;             //citire numar de intrebari

    for(i=1;i<=m;i++)
    {
        fin>>quest;     //citire tip de intrebare
        fin>>nr;        //citire valoare cautata
        gasit=0;

        if(quest==0)    //tratare intrebare tip 0
        {
            p=1;        //initializare interval de cautare
            u=n;
            while(p<=u) //cautarea se desfasoara cat timp intervalul de cautare e valid
            {
                mij=(u+p)/2;        //calcularea pozitiei de mijloc a intervalului
                if(x[mij]==nr)      //daca pozitia curenta contine exact valoarea cautata
                {
                    if(mij<u && x[mij]==x[mij+1])   //daca mai exista alta potrivire in dreapta pozitiei curente
                    {
                        p=mij+1;                    //continuam cautarea folosind pozitia din dreapta ca un nou inceput
                    }
                    else                            //daca nu mai exista alta potrivire in dreapta
                    {
                        gasit=1;                    //am gasit si tiparim pozitia
                        fout<<mij<<'\n';
                        break;
                    }
                }
                else
                    if(x[mij]<nr)   //daca pozitia curenta contine o valoare prea mica
                        p=mij+1;    //continuam cautarea folosind pozitia din dreapta ca un nou inceput de interval
                    else            //daca pozitia curenta contine o valoare prea mare
                        u=mij-1;    //continuam cautarea folosind pozitia din stanga ca un nou sfarsit de interval
            }

            if(gasit==0)            //daca se termina cautarea fara a gasi vreo potrivire, afisam -1
                fout<<-1<<'\n';
        }

        if(quest==1)            //tratare intrebare tip 1
        {
            p=1;                //initializare interval de cautare
            u=n;
            while(p<=u)         //cautarea se desfasoara cat timp intervalul de cautare e valid
            {
                mij=(u+p)/2;    //calcularea pozitiei de mijloc a intervalului
                if(x[mij]==nr)  //daca pozitia curenta contine exact valoarea cautata
                {
                    if(mij<u && x[mij]==x[mij+1])   //daca mai exista alta potrivire in dreapta pozitiei curente
                    {
                        p=mij+1;                    //continuam cautarea folosind pozitia din dreapta ca un nou inceput
                    }
                    else                            //daca nu mai exista alta potrivire in dreapta pozitiei curente
                    {
                        poz=mij;                    //am gasit valoarea exacta si retinem pozitia
                        break;
                    }
                }
                else
                    if(x[mij]<nr)   //daca pozitia curenta contine o valoare mai mica
                    {
                        poz=mij;    //retinem pozitia ca posibil candidat minor in caz ca nu vom gasi ceva mai bun
                        p=mij+1;    //si continuam cautarea folosind pozitia din dreapta ca un nou inceput
                    }
                    else            //daca pozitia curenta contine o valoare mai mare
                        u=mij-1;    //continuam cautarea folosind pozitia din stanga ca un nou sfarsit
            }
            fout<<poz<<'\n';        //afisam pozitia gasita
        }

        if(quest==2)                //tratare intrebare tip 2
        {
            p=1;                    //initializare interval de cautare
            u=n;
            while(p<=u)             //cautarea se desfasoara cat timp intervalul de cautare e valid
            {
                mij=(u+p)/2;        //calcularea pozitiei de mijloc a intervalului
                if(x[mij]==nr)      //daca pozitia curenta contine exact valoarea cautata
                {
                    if(mij>p && x[mij]==x[mij-1])   //daca mai exista alta potrivire in stanga pozitiei curente
                    {
                        u=mij-1;                    //continuam cautarea folosind pozitia din stanga ca un nou sfarsit
                    }
                    else                            //daca nu mai exista alta potrivire in stanga pozitiei curente
                    {
                        poz=mij;                    //am gasit valoarea exacta si retinem pozitia
                        break;
                    }
                }
                else
                    if(x[mij]>nr)       //daca pozitia curenta contine o valoare mai mare
                    {
                        poz=mij;        //retinem pozitia ca posibil candidat major in caz ca nu vom gasi ceva mai bun
                        u=mij-1;        //si continuam cautarea folosind pozitia din stanga ca un nou sfarsit
                    }
                    else                //daca pozitia curenta contine o valoare mai mica
                        p=mij+1;        //continuam cautarea folosind pozitia din dreapta ca un nou inceput
            }
            fout<<poz<<'\n';            //afisam pozitia gasita
        }
    }

    return 0;
}