#include <fstream>

using namespace std;

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

const int NMAX = 1e5 + 1;

int v[NMAX], n, m, q, val;

int bs0(int val)
{
    int left = 1, right = n, cand = -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (v[mid] <= val)
        {
            if (v[mid] == val && mid > cand)
                cand = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return cand;
}

int bs1(int val)
{
    int left = 1, right = n, cand = -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (v[mid] <= val)
        {
            if (mid > cand)
                cand = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    return cand;
}

int bs2(int val)
{
    int left = 1, right = n, cand = n + 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (v[mid] >= val)
        {
            if (mid < cand)
                cand = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return cand;
}

int main()
{
    fin >> n;

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

    fin >> m;

    while (m--)
    {
        fin >> q >> val;
        int ans = 0;
        if (q == 0)
            ans = bs0(val);
        else if (q == 1)
            ans = bs1(val);
        else
            ans = bs2(val);
        fout << ans << '\n';
    }

    return 0;
}