Description

Original source: USACO 2005 Feb. Gold

Farmer John has built a cottage with $n$ cow stalls arranged in a straight line. The $i$-th stall is located at position $x_i$. However, his $m$ cows are very unhappy with the cottage and often attack each other. To prevent the cows from harming one another, John decides to place each cow as far away from the others as possible. In other words, he wants to maximize the minimum distance between any two cows.

The cows dislike this arrangement, and if several cows are placed in the same stall, they will fight. To avoid any harm to the cows, John decides to assign the stalls himself so that the minimum distance between any two cows is as large as possible. What is this maximum possible minimum distance?

Input Format

The first line contains two integers $n$ and $m$, separated by a space;

The second line contains $n$ integers separated by spaces, representing the positions $x_i$.

Output Format

Output a single integer, representing the maximum possible minimum distance.

Sample 1

Placing the cows at positions $1$, $4$, and $8$ results in a minimum distance of $3$.

5 3
1 2 8 4 9

3

Constraints & Notes

$2 \leq n \leq 10^5$, $0 \leq x_i \leq 10^9$, $2 \leq m \leq n$.