#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\n", cautareBinaraTipUnu(sir, numarElemente, numar));
        }
        else if (tipIntrebare == 1)
        {
            fprintf(fisierIesire, "%ld\n", cautareBinaraTipDoi(sir, numarElemente, numar));
        }
        else if (tipIntrebare == 2)
        {
            fprintf(fisierIesire, "%ld\n", 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;
    unsigned int pozitie;

    while (stanga <= dreapta)
    {
        mijloc = stanga + (dreapta - stanga) / 2;

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

    return pozitie + 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 (stanga <= dreapta)
    {
        mijloc = stanga + (dreapta - stanga) / 2;

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

    return pozitie + 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 (stanga <= dreapta)
    {
        mijloc = stanga + (dreapta - stanga) / 2;

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

    return pozitie + 1;
}