#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[10000000];

int main()
{
    int n, m, i, x, tip, a;
    in >> n;
    for (i = 1; i <= n; i++)
        in >> v[i];
    in >> m;
    for (i = 1; i <= m; i++)
    {
        in >> tip >> x;
        if (tip == 0)
        {
            int pos = upper_bound(v + 1, v + n + 1, x + 1) - v - 1;
            if (v[pos] == x)
            {
                out << pos << '\n';
            }
            else
            {
                out << -1 << '\n';
            }
        }
        if (tip == 1)
        {
            out << upper_bound(v + 1, v + n + 1, x) - v - 1 << '\n';
        }
        if (tip == 2)
        {
            out << lower_bound(v + 1, v + n + 1, x) - v << '\n';
        }
    }
    return 0;
}