136. Aggressive Cows

Given positions of n stalls and c cows, place the cows so that the minimum distance between any two is maximized. Return that largest minimum distance. Input: '[stalls], c'.

Input: '[stalls], c'.

Output: Integer — largest minimum distance.

Examples

Input: [1,2,4,8,9], 3
Output: 3
Explanation: Place at 1,4,8 -> min dist 3.

Input: [1,2,8,4,9], 3
Output: 3
Explanation: Same after sorting.

Input: [1,5,10], 2
Output: 9
Explanation: Place at 1 and 10.

Constraints

• 1<=n<=10^5
• 2<=c<=n
• 0<=stalls[i]<=10^9

Asked by