private static int binSearchFirst(final int key, final int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            var mid = lo + (hi - lo) / 2;
 
            if (key > arr[mid]) {
                lo = mid + 1;
            } else if (key < arr[mid]
                || (mid > 0 && arr[mid - 1] == key)) {
 
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }