#include <fstream>

using namespace std;

int n, tomb[100000];

// A legnagyobb pozicio, amely x vagy ha nincs ilyen akkor teritsen vissza -1
int binarySearch(int x)
{
    int jobb = n - 1, bal = 0;

    while (bal < jobb)
    {
        int kozep = (jobb + bal + 1) / 2; // jobbra huz

        if (tomb[kozep] <= x)
        {
            bal = kozep;
        }
        else
        {
            jobb = kozep - 1;
        }
    }
    // bal == jobb
    if (tomb[jobb] == x)
        return jobb + 1; // Azert kell a +1 mivel infoarenan a tomb 1-tol indul, nem 0-tol

    return -1;
}

//--------------------------------------------------------------------------------------------

int binarySearch1(int x)
{

    int jobb = n - 1, bal = 0;

    while (bal < jobb)
    {
        int kozep = (jobb + bal + 1) / 2; // jobbra huz

        if (tomb[kozep] <= x)
        {
            bal = kozep;
        }
        else
        {
            jobb = kozep - 1;
        }
    }

    return jobb + 1; // Azert kell a +1 mivel infoarenan a tomb 1-tol indul, nem 0-tol
}

//--------------------------------------------------------------------------------------------

int binarySearch2(int x)
{

    int jobb = n - 1, bal = 0;

    while (bal < jobb)
    {
        int kozep = (jobb + bal) / 2; // balra huz

        if (tomb[kozep] < x)
        {
            bal = kozep + 1;
        }
        else
        {
            jobb = kozep;
        }
    }

    return jobb + 1; // Azert kell a +1 mivel infoarenan a tomb 1-tol indul, nem 0-tol

    return -1;
}

//--------------------------------------------------------------------------------------------

int main()
{

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

    int m, tipus, x, eredmeny = -1;
    in >> n;

    for (int i = 0; i < n; i++)
    {
        in >> tomb[i];
    }

    in >> m;
    for (int i = 0; i < m; i++)
    {
        in >> tipus >> x;

        if (tipus == 0)
        {
            eredmeny = binarySearch(x);
        }
        else if (tipus == 1)
        {
            eredmeny = binarySearch1(x);
        }
        else
        {
            eredmeny = binarySearch2(x);
        }

        out << eredmeny << "\n";
    }

    return 0;
}