Boosting the Weakest House on the Lane

Houses stand at positions 0 .. n-1 along a lane, and boosters[i] signal boosters are already mounted at house i. A booster at position p serves every house j with |p - j| <= r. The signal of a house is the number of boosters that serve it.

You may mount up to k extra boosters at any houses (several at the same house is fine). Return the largest possible value of the minimum signal over all houses.

Examples

Input:  boosters = [1, 2, 4, 5, 0], r = 1, k = 2
Output: 5
Explanation: the signals are [3, 7, 11, 9, 5]. Mounting both extras at house 1 gives
[5, 9, 13, 9, 5]. Reaching 6 would need 3 more at the left end and 1 at the right.

Input:  boosters = [0, 0, 0, 0, 0, 0, 0], r = 2, k = 2
Output: 1
Explanation: extras at houses 2 and 5 serve houses 0-4 and 3-6.

Constraints

• 1 <= n = len(boosters) <= 10**4, 0 <= boosters[i] <= 10**5
• 0 <= r <= n, 0 <= k <= 10**9
• Adding the extras one at a time, or trying every target value, is too slow for the largest tests.

Goals

• Pair a maximise-the-minimum search with a greedy feasibility sweep
• Place each new item as far right as it can usefully go, and expire its effect with a difference array