A food critic gives one whole-number rating per day, listed in ratings. The magazine will feature a
contiguous stretch of at least k days, and the headline is the stretch's median: sort
the stretch and take the middle value, and for an even length take the lower of the two middle
values.
Return the largest headline median over all allowed stretches.
Examples
Input: ratings = [1, 5, 2, 6, 3], k = 3
Output: 5
Explanation: the stretch [5, 2, 6] sorts to [2, 5, 6], median 5.
Input: ratings = [4, 4, 1, 1, 9], k = 2
Output: 4
Explanation: [1, 9] has median 1 (the lower middle value). [4, 4] gives 4.
Constraints
1 <= k <= len(ratings) <= 3 * 10**4-10**9 <= ratings[i] <= 10**9- Sorting every stretch, or even one stretch per start, is too slow for the largest tests.
Goals
- Replace 'median at least x' by a sum test on +1 / -1 values
- Search the answer over the sorted distinct values of the input