Question
Hostile Cows
You are given an array of KaTeX can only parse string typed expression integers representing the positions of stalls on a number line. You want to place KaTeX can only parse string typed expression cows in these stalls such that the minimum distance between any two cows is as large as possible.
Your task is to find the largest possible minimum distance between any two cows.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of stalls and the number of cows.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression, where KaTeX can only parse string typed expression represents the position of the KaTeX can only parse string typed expression-th stall.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression, where KaTeX can only parse string typed expression represents the position of the KaTeX can only parse string typed expression-th stall.
Output
Print a single integer — the largest minimum distance between any two cows.
Example
Input
5 3
1 2 8 4 9
Output
3
Explanation
We can place cows at positions 1, 4, and 8 (or 1, 4, 9).
The minimum distance between any two cows is 3, which is the largest possible.
5 3
1 2 8 4 9
Output
3
Explanation
We can place cows at positions 1, 4, and 8 (or 1, 4, 9).
The minimum distance between any two cows is 3, which is the largest possible.