Place servers as far apart as possible

Problem

A data centre has n rack positions on a line. Choose k of them for servers so that the smallest distance between any two chosen servers is as large as possible. Print that largest smallest distance.

Input, output and limits

Input: Line 1: n and k. Line 2: n different rack positions, in any order.
Output: One integer: the largest possible smallest distance.
Constraints: 2 ≤ k ≤ n ≤ 10^5
0 ≤ position ≤ 10^9, all positions are different

Examples

Example

Input

5 3
1 2 8 4 9

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Sort the positions. For a distance d, place the first server at the leftmost rack and then at each next rack that is at least d away. If you place k servers, d is possible.

Hint 2

A larger d is harder to satisfy, so search for the last d that works.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems