#include <fstream>
#include <algorithm>

using namespace std;

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

int A[100005], m, n;

int main()
{
    f >> n;
    for(int i = 1; i <= n; i ++)
        f >> A[i];

    f >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        f >> x >> y;

        if(x == 0)
        {
            int p = upper_bound(A + 1, A + n + 1, y) - A;
            if(p <= n + 1 && p > 1 && A[p - 1] == y)
                g << p - 1 << '\n';
            else
                g << -1 << '\n';
        }

        else if(x == 1)
        {
            int p = upper_bound(A + 1, A + n + 1, y) - A;
            g << p - 1 << '\n';
        }

        else
        {
            int p = lower_bound(A + 1, A + n + 1, y) - A;
            g << p << '\n';
        }
    }
    return 0;
}