#include <fstream>

using namespace std;

int v[100001];
int n, m, tip, valoare;

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

int cautbin0 (int cheie)
{
    int mijloc, primul=1, ultimul=n;

    while (primul <= ultimul)
    {
        mijloc = (primul + ultimul) / 2;
        if (v[mijloc] <= cheie)
            primul = mijloc + 1;
        else
            ultimul = mijloc - 1;
    }
    mijloc = (primul + ultimul) / 2;

    if (v[mijloc] > cheie) mijloc --;
    if (v[mijloc] == cheie)
        return mijloc;
    return -1;
}

int cautbin1 (int cheie)
{
    int primul=1, ultimul=n, mijloc;

    while (primul < ultimul)
    {
        mijloc = (primul + ultimul) / 2;
        if (v[mijloc] <= cheie)
            primul = mijloc + 1;
        else
            ultimul = mijloc;
    }

    mijloc = (primul + ultimul) / 2;
    if (v[mijloc] > cheie)
        -- mijloc;
    return mijloc;
}

int cautbin2 (int cheie)
{
    int mijloc, primul=1, ultimul=n;

    while (primul < ultimul)
    {
        mijloc = (primul + ultimul) / 2;
        if (v[mijloc] < cheie)
            primul = mijloc + 1;
        else
            ultimul = mijloc;
    }

    mijloc = (primul + ultimul) / 2;
    if (v[mijloc] < cheie)
        ++ mijloc;
    return mijloc;
}

int main ()
{
    in>>n;
    int i;
    for (i = 1; i <= n; ++ i)
        in>>v[i];

    in>>m;

    for(i=1;i<=m;i++)
    {
        in>>tip>>valoare;
        if (tip == 0)
            out<<cautbin0(valoare)<<"\n";
        if (tip == 1)
            out<<cautbin1(valoare)<<"\n";
        if (tip == 2)
            out<<cautbin2(valoare)<<"\n";
    }
    return 0;
}

/*
//old (corect, dar ineficient)
#include <fstream>

#include <iostream>

using namespace std;

int v[100001];
int n, m;

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

int cautbin0 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    if(x<v[inceput]||x>v[sfarsit])
        return -1;
    while(x!=v[inceput]&&x!=v[sfarsit]&&x!=v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(x==v[inceput])
            pozitie=inceput;
        if(x==v[mijloc])
            pozitie=mijloc;
        if(x==v[sfarsit])
            pozitie=sfarsit;
    }
    if(x==v[inceput])
        pozitie=inceput;
    if(x==v[mijloc])
        pozitie=mijloc;
    if(x==v[sfarsit])
        pozitie=sfarsit;
    pozitie++;
    while(x==v[pozitie])
        pozitie++;
    pozitie--;
    return pozitie;
}

int cautbin1 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    while(x>v[inceput]&&x>v[sfarsit]&&x>v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(v[inceput]<=x)
            pozitie=inceput;
        if(v[mijloc]<=x)
            pozitie=mijloc;
        if(v[sfarsit]<=x)
            pozitie=sfarsit;
    }
    if(v[inceput]<=x)
            pozitie=inceput;
    if(v[mijloc]<=x)
            pozitie=mijloc;
    if(v[sfarsit]<=x)
            pozitie=sfarsit;
    pozitie++;
    while(v[pozitie]<=x)
        pozitie++;
    pozitie--;
    return pozitie;
}

int cautbin2 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    while(x<v[inceput]&&x<v[sfarsit]&&x<v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(v[inceput]>=x)
            pozitie=inceput;
        if(v[mijloc]>=x)
            pozitie=mijloc;
        if(v[sfarsit]>=x)
            pozitie=sfarsit;
    }
    if(v[inceput]>=x)
            pozitie=inceput;
    if(v[mijloc]>=x)
            pozitie=mijloc;
    if(v[sfarsit]>=x)
            pozitie=sfarsit;
    pozitie--;
    while(v[pozitie]>=x)
        pozitie--;
    pozitie++;
    return pozitie;
}

int main()
{
    in>>n;
    int i, tip, numar;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>tip>>numar;
        if(tip==0)
            out<<cautbin0(numar)<<"\n";
        if(tip==1)
            out<<cautbin1(numar)<<"\n";
        if(tip==2)
            out<<cautbin2(numar)<<"\n";

    }
    return 0;
}

*/