Aggressive Cows

You are given n cows and k stakes located at various positions. Each stake can have at most one cow tied to it. Because the cows are aggressive, you want to maximize the minimum distance between any two cows. In other words, determine the largest possible minimum distance at which all cows can be placed on the stakes.

Problem Details:

• You are given n (number of cows) and k (number of stakes).
• The positions of the k stakes are provided. You can assume these positions are integers and may not be in sorted order.
• Your task is to assign cows to different stakes such that the minimum distance between any two cows is as large as possible, and then output this distance.

Mathematical Formulation:

Let the positions be sorted as \(x_1 \le x_2 \le \cdots \le x_k\). We wish to choose n positions \(x_{i_1}, x_{i_2}, \ldots, x_{i_n}\) such that the quantity \[ d = \min_{1 \le j < n} \left(x_{i_{j+1}} - x_{i_j}\right) \] is maximized.

inputFormat

The first line contains two integers, n and k, representing the number of cows and the number of stakes respectively.

The second line contains k integers, each representing the position of a stake.

outputFormat

Output a single integer representing the largest possible minimum distance between any two cows when placed optimally.

sample

4 6
0 3 4 7 8 9

2