#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int n, m, t, x, mid, p, u, v[100001];
int main()
{
    in >> n;
    for (int i = 1; i <= n; i++) in >> v[i];
    in >> m;
    for (int i = 1; i <= m; i++)
    {
        in >> t >> x;
        p = 1; u = n;
        if (t == 0)
        {
            while (p <= u)
            {
                mid = (p + u) / 2;
                if (v[mid] <= x) p = mid + 1;
                else u = mid - 1;
            }
            mid = (p + u) / 2;
            if (v[mid] > x) mid--;
            if (v[mid] == x) out << mid << '\n';
            else out << -1 << '\n';
        }
        if (t == 1)
        {
            while (p < u)
            {
                mid = (p + u) / 2;
                if (v[mid] <= x) p = mid + 1;
                else u = mid;
            }
            mid = (p + u) / 2;
            if (x < v[mid]) mid--;
            out << mid << '\n';
        }
        if (t == 2)
        {
            while (p < u)
            {
                mid = (p + u) / 2;
                if (v[mid] < x) p = mid + 1;
                else u = mid;
            }
            mid = (p + u) / 2;
            if (v[mid] < x) mid++;
            out << mid << '\n';
        }
    }
    out.close(); return 0;
}