#include <fstream>

using namespace std;

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

int cb1(int v[], int n, int x)
{
    int st, dr, mid, p = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (x == v[mid])
        {
            p = mid;
            st = mid + 1;
        }
        else if (x < v[mid])
            dr = mid - 1;
        else
            st = mid + 1;
    }
    return p;
}

int cb2(int v[], int n, int x)
{
    int st, dr, mid, p;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (x >= v[mid])
        {
            p = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return p;
}

int cb3(int v[], int n, int x)
{
    int st, dr, mid, p;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (x <= v[mid])
        {
            p = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }
    return p;
}

int v[100001];

int main()
{
    int N, M, i;

    in >> N;
    for (i = 1; i <= N; ++i)
        in >> v[i];
    in >> M;
    for (i = 1; i <= M; ++i)
    {
        int C, X;
        in >> C >> X;
        if (C == 0)
            out << cb1(v, N, X) << '\n';
        else if (C == 1)
            out << cb2(v, N, X) << '\n';
        else
            out << cb3(v, N, X) << '\n';
    }

    in.close();
    out.close();
    return 0;
}