def find_low_index(arr, key):
    """Find the low index of the key in the array arr.

    Time:  O(log n)
    Space: O(1)
    """
    lo, hi = 0, len(arr)
    while lo < hi:
        mi = (lo + hi) // 2
        if arr[mi] < key:
            lo = mi + 1
        elif arr[mi] == key and (mi == 0 or arr[mi - 1] < key):
            return mi
        else:
            hi = mi
    return -1