538. Minimize Max Distance Between Gas Stations (Exact)

Given sorted gas station positions and k additional stations to place anywhere, minimize the maximum distance between adjacent stations. For an exact integer answer, distances are scaled by 1,000,000 — return the minimized maximum adjacent distance multiplied by 1,000,000 (the smallest scaled distance d for which k stations suffice). Input: '[stations], k'.

Input: '[stations], k'.

Output: Integer — the minimized maximum distance scaled by 10^6.

Examples

Input: [1,2,3,4,5,6,7,8,9,10], 9
Output: 500001
Explanation: Optimal ~0.5, scaled.

Input: [0,100], 1
Output: 50000001
Explanation: One station splits 100 into ~50.

Input: [1,5], 3
Output: 1000001
Explanation: Three stations split gap 4 into ~1.

Constraints

• 1<=n<=10^4
• 0<=k<=10^6
• sorted positions

Asked by