#include <iostream>
#include <fstream>

using namespace std;

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

int n, t, a, val;
int v[100010];

int bsearch0 (int p, int u, int x)
{
    int m;

    while (p <= u)
    {
        m = (p + u) / 2;

        if (v[m] <= x)
            p = m + 1;

        else

            u = m - 1;
    }

    m = (p + u) / 2;

    if (v[m] > x)
        m--;

    if (v[m] == x)
        return m;

    return -1;
}

int bsearch1 (int p, int u, int x)
{
    int m;

    while (p < u)
    {
        m = (p + u) / 2;

        if (v[m] <= x)
            p = m + 1;

        else

            u = m;
    }

    m = (p + u) / 2;

    if (v[m] > x)
        m--;

        return m;
}

int bsearch2 (int p, int u, int x)
{
    int m;

    while (p < u)
    {
        m = (p + u) / 2;

        if (v[m] < x)
            p = m + 1;

        else

            u = m;
    }

    m = (p + u) / 2;

    if (v[m] < x)
        m++;

        return m;
}

int main()
{
    in >> n;

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

    in >> t;

    for (int i = 1; i <= t; i++)
    {
        in >> a >> val;

       if (a == 0)
        out << bsearch0 (1, n, val) << '\n';

        if (a == 1)
        out << bsearch1 (1, n, val) << '\n';

         if (a == 2)
        out << bsearch2 (1, n, val) << '\n';
    }

    return 0;
}