#include <stdio.h>
#include <stdbool.h>

const unsigned long int SIR_MAX = 100000;

long int cautareBinaraTipUnu(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar);
long int cautareBinaraTipDoi(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar);
long int cautareBinaraTipTrei(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar);

int main()
{
    FILE* fisierIntrare;
    FILE* fisierIesire;

    unsigned long int numarElemente;
    unsigned long int sir[SIR_MAX];
    unsigned long int numarIntrebari;
    unsigned short int tipIntrebare;
    unsigned long int numar;

    fisierIntrare = fopen("cautbin.in", "r");
    fisierIesire = fopen("cautbin.out", "w");

    fscanf(fisierIntrare, "%lu", &numarElemente);
    for (unsigned long int index = 0; index < numarElemente; index++)
    {
        fscanf(fisierIntrare, "%lu", &sir[index]);
    }

    fscanf(fisierIntrare, "%lu", &numarIntrebari);
    for (unsigned long int index = 0; index < numarIntrebari; index++)
    {
        fscanf(fisierIntrare, "%hu", &tipIntrebare);
        fscanf(fisierIntrare, "%lu", &numar);

        if (tipIntrebare == 0)
        {
            fprintf(fisierIesire, "%ld", cautareBinaraTipUnu(sir, numarElemente, numar));
        }
        else if (tipIntrebare == 1)
        {
            fprintf(fisierIesire, "%ld", cautareBinaraTipDoi(sir, numarElemente, numar));
        }
        else if (tipIntrebare == 2)
        {
            fprintf(fisierIesire, "%ld", cautareBinaraTipTrei(sir, numarElemente, numar));
        }
    }
}

long int cautareBinaraTipUnu(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar)
{
    unsigned long int stanga = 0;
    unsigned long int dreapta = numarElemente;
    unsigned int mijloc;

    while (true)
    {
        if (stanga > dreapta)
        {
            return -1;
        }
        else
        {
            mijloc = stanga + (dreapta - stanga) / 2;

            if (sir[mijloc] == numar)
            {
                if (sir[mijloc + 1] == numar)
                {
                    stanga = mijloc + 1;
                }
                else
                {
                    return mijloc + 1;
                }
            }
            else
            {
                if (sir[mijloc] > numar)
                {
                    dreapta = mijloc - 1;
                }
                else
                {
                    stanga = mijloc + 1;
                }
            }
        }
    }
}

long int cautareBinaraTipDoi(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar)
{
    unsigned long int stanga = 0;
    unsigned long int dreapta = numarElemente;
    unsigned int mijloc;
    unsigned int pozitie;

    while (true)
    {
        if (stanga > dreapta)
        {
            return pozitie + 1;
        }
        else
        {
            mijloc = stanga + (dreapta - stanga) / 2;

            if (sir[mijloc] <= numar)
            {
                stanga = mijloc + 1;
                pozitie = mijloc;
            }
            else
            {
                dreapta = mijloc - 1;
            }
        }
    }
}

long int cautareBinaraTipTrei(unsigned long int sir[SIR_MAX], unsigned long int numarElemente, unsigned long int numar)
{
    unsigned long int stanga = 0;
    unsigned long int dreapta = numarElemente;
    unsigned int mijloc;
    unsigned int pozitie;

    while (true)
    {
        if (stanga > dreapta)
        {
            return pozitie + 1;
        }
        else
        {
            mijloc = stanga + (dreapta - stanga) / 2;

            if (sir[mijloc] >= numar)
            {
                dreapta = mijloc - 1;
                pozitie = mijloc;
            }
            else
            {
                stanga = mijloc + 1;
            }
        }
    }
}