eolymp
bolt
Try our new interface for solving problems
Problems

Ice-Cream

Ice-Cream

Time limit 1 second
Memory limit 128 MiB

The beach stretches along the seacoast like a narrow strip. At some points of the beach the ice cream stalls are located. One day not all the ice cream sellers come to work. Distribute the sellers among the ice-cream stalls so that the minimum distance between them is as much as possible. So they will interfere less with each other.

Input data

The first line contains the number of stalls n (2 < n < 10001) and the number of ice cream sellers k (1 < k < n) at work. The second line contains n positive integers in increasing order - the coordinates of the stalls (the coordinates are not greater than 10^9).

Output data

Print one number - the minimum distance between the adjacent stalls in the optimal arrangement.

Examples

Input example #1
5 3
1 2 3 100 1000
Output example #1
99
Input example #2
8 4
2 7 10 15 18 22 25 27
Output example #2
8