140. Minimize Max Distance to Gas Station

Given sorted gas station positions and k new stations to add, minimize the maximum distance between adjacent stations. Return the minimized maximum distance scaled by 10^6 and rounded to the nearest integer (to keep deterministic integer output). Input: '[stations], k'.

Input: '[stations], k'.

Output: Integer — minimized max distance times 10^6.

Examples

Input: [1,2,3,4,5,6,7,8,9,10], 9
Output: 500000
Explanation: Half-unit spacing -> 0.5 * 10^6.

Input: [1,100], 1
Output: 49500000
Explanation: 49.5 * 10^6.

Constraints

• 2<=stations.length<=2000
• 0<=stations[i]<=10^8
• 1<=k<=10^6

Asked by