Aggressive Cows

Farmer John has built a barn with n cow sheds, arranged in a straight line. The i-th cow shed is located at position $x_i$. However, his m cows are dissatisfied with the barn and frequently clash with each other. To prevent injuries, John wants to assign each cow a separate cow shed such that the minimum distance between any two cows is maximized. In other words, you need to maximize the minimum distance between any two cows.

This problem can be mathematically formulated as follows: find the largest value d such that it is possible to place m cows in the sheds at positions $x_1, x_2, \dots, x_n$ with a minimum pairwise distance of at least $d$.

Note: If multiple cows are placed too close together in one shed, they will fight. Thus, the cows must be placed in separate sheds.

inputFormat

The first line of input contains two space-separated integers n and m $(2 \leq m \leq n \leq 10^5)$, where n is the number of cow sheds and m is the number of cows.

The second line contains n space-separated integers $x_1, x_2, \dots, x_n$ $(0 \leq x_i \leq 10^9)$, which represent the positions of the cow sheds. These positions may not be in sorted order.

outputFormat

Output a single integer, the largest minimum distance between any two cows when they are optimally placed in the cow sheds.

sample

5 3
1 2 8 4 9

3