A tide gauge logged integer water levels levels. An engineer wants to recalibrate one stretch of
exactly k consecutive readings so that they all show the same integer value. Changing a reading
by d units costs |d|, so the cost of a stretch is the smallest possible total change.
Return [cost, start] for the cheapest stretch, where start is the index of its first reading.
If several stretches share the lowest cost, return the one with the smallest start.
Examples
Input: levels = [4, 1, 7, 3, 3, 9], k = 3
Output: [4, 2]
Explanation: [4, 1, 7] costs 6, [1, 7, 3] costs 6, [7, 3, 3] costs 4 (set all to 3),
[3, 3, 9] costs 6.
Input: levels = [5, 5, 5, 1], k = 4
Output: [4, 0]
Explanation: the only stretch; setting every reading to 5 costs 4.
Constraints
1 <= k <= len(levels) <= 2 * 10**5-10**9 <= levels[i] <= 10**9- Sorting every stretch separately is far too slow for the largest tests.
Goals
- Keep a sliding window split into a lower and an upper half with two heaps
- Delete leaving readings lazily, while live sizes and sums stay exact
- Price a window from its median and the two half sums in O(1)