Aggressive Cows

Problem statement

A livestock center places territorial cows in stalls along a straight lane. To keep every pair of neighboring occupied stalls sufficiently separated, the manager wants the placement whose closest pair is as far apart as possible. Your task Place k cows in distinct given stall positions and maximize the minimum distance between any two placed cows. Important details Stall positions may arrive unsorted, but each position is distinct. A stall holds at most one cow. You may leave stalls empty; choose the placement rather than forcing the cows into consecutive input entries. Worked example For positions [1, 3, 6, 10] and three cows, choosing 1, 6 and 10 gives distances 5 and 4, so the minimum is 4. No placement gives a larger minimum.

Input format

First line: n k. Next line: n distinct stall coordinates.

Output format

Print the largest possible minimum distance.

Constraints

2 <= k <= n <= 100000; 0 <= coordinates <= 1000000000.

Sample input

4 3
1 3 6 10

Sample output

4