#include <fstream>

using namespace std;

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

#define MAXN 100005

int v[MAXN];

int i = 1, m;

int cautbin(int u, int x)
{
    while (i <= u)
    {
        m = (i + u) / 2;
        if (v[m] <= x)
            i = m + 1;
        else
            u = m - 1;
    }

    m = (i + u) / 2;

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

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

    else
        return -1;
}

int cautbin2(int u, int x)
{
    int n = u;

    while (i < u)
    {
        m = (i + u) / 2;
        if (v[m] <= x)
            i = m + 1;
        else
            u = m;
    }

    m = (i + u) / 2;

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

    return m;
}

int cautbin3(int u, int x)
{
    while (i < u)
    {
        m = (i + u) / 2;

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

        else
            u = m;
    }

    m = (i + u) / 2;

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

    return m;
}

int main ()
{

    int n, t, c, x;
    cin >> n;

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

    cin >> t;

    while(t--)
    {
        cin >> c >> x;

        if (c == 0)
            cout << cautbin(n, x) << "\n";
        if (c == 1)
            cout << cautbin2(n, x) << "\n";
        if (c == 2)
            cout << cautbin3(n, x) << "\n";
    }

    return 0;
}