490. Minimize Maximum Distance to Gas Station (Scaled)

Given sorted positions of gas stations and k additional stations you may place anywhere, minimize the maximum distance between adjacent stations. To keep the answer an exact integer, distances are scaled by 1000 — return the minimized maximum adjacent distance multiplied by 1000 (i.e. the smallest scaled distance d, in thousandths, for which k stations suffice). Input: '[stations], k'.

Input: '[stations], k'.

Output: Integer — the minimized maximum distance scaled by 1000.

Examples

Input: [1,2,3,4,5,6,7,8,9,10], 9
Output: 501
Explanation: Optimal max distance ~0.5 (scaled to 501).

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

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

Constraints

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

Asked by