Aggressive Cows

You are given n stalls located at various positions on a straight line and c cows. Your task is to place the cows into these stalls such that the minimum distance between any two cows is as large as possible. Formally, if the stalls are located at positions \(a_1, a_2, \ldots, a_n\) (not necessarily in order), you need to choose c positions to maximize the value of \(d\), where \(d = \min_{\text{any two cows}}|a_j - a_i|\). Use binary search to determine the largest possible \(d\).

inputFormat

The first line contains two space-separated integers n and c, representing the number of stalls and the number of cows, respectively. The second line contains n space-separated integers representing the positions of the stalls.

outputFormat

Output a single integer: the largest minimum distance possible between any two cows.

5 3
1 2 8 4 9

3