#include <fstream>
using namespace std;

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

int sir[100001];

int cautare_binara_0 (int dreapta , int valoare)
{
    int step = 1 , indice = 0;
    while (step < dreapta)
        step <<= 1;
    while (step)
    {
        if (indice + step <= dreapta && sir[indice + step] <= valoare)
            indice += step;
        step >>= 1;
    }

    if (sir[indice] == valoare)
        return indice;

    return -1;
}

int cautare_binara_1 (int stanga , int dreapta , int valoare)
{
    int pozitie = 0;
    while (stanga <= dreapta)
    {
        int mijloc = (1LL * stanga + dreapta) / 2;

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

    return pozitie;
}

int cautare_binara_2 (int stanga , int dreapta , int valoare)
{
    int pozitie = 0;
    while (stanga <= dreapta)
    {
        int mijloc = (1LL * stanga + dreapta) / 2;

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

    return pozitie;
}

int main ()
{
    int lungime;
    cin >> lungime;

    for (int indice = 1 ; indice <= lungime ; indice++)
        cin >> sir[indice];
    
    int intrebari , tip;
    cin >> intrebari;

    int valoare;
    for (int indice = 1 ; indice <= intrebari ; indice++)
    {
        cin >> tip >> valoare;
        tip == 0 ? cout << cautare_binara_0 (lungime , valoare) << '\n' :
        tip == 1 ? cout << cautare_binara_1 (0 , lungime - 1 , valoare) << '\n' :
                   cout << cautare_binara_2 (0 , lungime - 1 , valoare) << '\n';
    }

    cout.close(); cin.close();
    return 0;
}