550. Maximize the Minimum Powered City

Cities lie in a row, each with some power stations. A station in city i powers every city within distance r (so city j receives power from all stations within range r). You may build k additional stations, each placed in any city. Maximize the minimum power among all cities and return that maximized minimum. The input is JSON {stations, r, k}.

Input: JSON {stations, r, k}.

Output: Integer — the maximized minimum power.

Examples

Input: {"stations":[1,2,4,5,0],"r":1,"k":2}
Output: 5
Explanation: Optimal placement raises the minimum to 5.

Input: {"stations":[4,4,4,4],"r":0,"k":3}
Output: 4
Explanation: Already balanced; extra stations help least-powered cities.

Input: {"stations":[1],"r":1,"k":1}
Output: 2
Explanation: Add one station to the single city.

Constraints

• 1<=n<=10^5
• 0<=r<n
• 0<=k<=10^9

Asked by