692. Maximizing Minimum Distance for Aggressive Horses

0

Easy

Given an array of N integers representing the positions of stalls, and an integer k representing the number of aggressive horses, the task is to assign stalls to the horses in a way that maximizes the minimum distance between any two horses.

Input Format

The input consists of two space-separated integers n and k on the first line, representing the number of stalls and the number of aggressive horses, respectively. The second line contains n space-separated integers denoting the positions of the stalls.

Output Format

Print the minimum distance between the assigned horses.

Example

Input

5 3
1 2 4 8 9

Output

3

Constraints

2 <= n <= 10^5

2 <= k <= n

0 <= stalls[i] <= 10^9

2 <= k <= n

0 <= stalls[i] <= 10^9

Loading...

View Submissions

Console