Aggressive Cows

Farmer John has built a barn with \(N\) stalls located on a straight line with positions \(x_1, x_2, \dots, x_N\) where \(0 \leq x_i \leq 10^9\) and \(2 \leq N \leq 10^5\). He wants to place his \(C\) cows (where \(2 \leq C \leq N\)) into these stalls in such a way that the minimum distance between any two cows is as large as possible. Compute the largest minimum distance possible between any two cows.

The problem essentially asks to maximize the value of \(d\) such that it is possible to place all \(C\) cows in the stalls with each pair of adjacent cows separated by at least \(d\), i.e.:

[ \min_{1 \leq i < C} (position_{i+1} - position_i) \geq d ]

You are to determine this maximum \(d\).

inputFormat

The first line of input contains two integers \(N\) and \(C\) separated by a space.

The second line contains \(N\) integers representing the coordinates of the stalls separated by spaces.

outputFormat

Output a single integer which is the largest minimum distance possible between any two of the placed cows.

sample

5 3
1 2 8 4 9

3