#include <fstream>

using namespace std;

const int N = 1e5;

int v[N];

int caut_bin_ultim(int v[], int n, int val)
{
    ///pozitia ultimului element al lui v care e <= val
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] <= val)
        {
            rez = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return rez;
}

int caut_bin_prim(int v[], int n, int val)
{
    ///pozitia primului element al lui v care e >= val
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] >= val)
        {
            rez = m;
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }
    return rez;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> v[i];
    }
    int q;
    in >> q;
    for (int i = 0; i < q; i++)
    {
        int tip, val;
        in >> tip >> val;
        if (tip == 0 || tip == 1)
        {
            int p = caut_bin_ultim(v, n, val);
            if (tip == 0 && v[p] < val)
            {
                p = -1;
            }
            else
            {
                p++;
            }
            out << p << "\n";
        }
        else
        {
            int p = caut_bin_prim(v, n, val);
            out << p + 1 << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}