#include <fstream>
#include <iostream>

using namespace std;

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

const int NMAX = 1e5 + 1;

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

int bin_search_bits(int val)
{
    int ans = 0, start_pos = 1;
    while ((start_pos << 1) <= n)
        start_pos <<= 1;
    while (start_pos)
    {
        // int crt = ans + start_pos;
        int crt = ans | start_pos;
        if (crt <= n && v[crt] <= val)
            ans = crt;
        start_pos >>= 1;
    }
    if (v[ans] == val)
        return ans;
    return -1;
}

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 = bin_search_bits(val);
        else if (q == 1)
            ans = bs1(val);
        else
            ans = bs2(val);
        fout << ans << '\n';
    }

    return 0;
}