Earliest Harvest Day

A row of plots is planted; ripe[i] is the day plot i becomes ripe. To fill an order you need bunches bunches, and each bunch must be picked from size adjacent plots that are all ripe. A plot can be used in at most one bunch. Return the earliest day on which the order can be filled, or -1 if it never can.

Examples

Input:  ripe = [1, 10, 3, 10, 2], bunches = 3, size = 1
Output: 3

Input:  ripe = [1, 10, 3, 10, 2], bunches = 3, size = 2
Output: -1
Explanation: five plots can never give three disjoint pairs.

Input:  ripe = [7, 7, 7, 7, 12, 7, 7], bunches = 2, size = 3
Output: 12

Constraints

• 1 <= len(ripe) <= 5 * 10**4, 1 <= ripe[i] <= 10**9
• 1 <= bunches, size <= len(ripe)
• Required time: O(n log(max(ripe))).

Goals

• Check feasibility with a single pass that tracks runs of adjacent items
• Detect impossibility before searching