Description

Farmer John built a barn with $n$ stalls arranged on a straight line; the $i$-th stall is at position $x_i$. His $m$ cows are unhappy and often fight, so he wants to place them so that each cow is as far as possible from the others. In other words, he wants to maximize the minimum distance between any two cows.

Cows do not like this layout, and if multiple cows share a stall, they will fight. To prevent conflicts, each stall can hold at most one cow. Determine the largest possible value of the minimum distance between any two cows.

Input Format

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain one integer $x_i$, representing the position of a stall.

Output Format

Output a single integer: the maximum possible minimum distance.

5 3
1
2
8
4
9

3

Hint

Sample Explanation: Place the cows at positions $1$, $4$, and $8$; the minimum distance is $3$. It is easy to prove that this minimum distance is already maximized.

Constraints: For $100\%$ of the testdata, $2 \le n \le 10^5$, $0 \le x_i \le 10^9$, $2 \le m \le n$. The array $x$ is not guaranteed to be in nondecreasing order.

Translated by ChatGPT 5