Bill has taken a liking to horticulture and has a number of flower pots lined up horizontally against the window as shown below:

Suppose Bill has 9 flower pots but only pots 1, 2, 4, 8, and 9 are suitable for planting. Since flowers need space to flourish, Bill wants to maximize the number of pots between each flower (that is the minimum distance between any two consecutive flowers is maximized). Given that he wants to place 3 flowers in the usable pots above, the optimal minimum gap would be 2 (ie. he places flowers in pots 1, 4, and 9).

Because Bill is too busy downloading memes and taking care of this flowers, he needs you to write a program that given a certain number of pots and flowers, this program determines the optimal minimum number of pots between each flower.

Input

You will be given multiple sets of pots and flowers in the following format:

Pots Flowers
Pot1
Pot2
...
PotN

The first line contains the number of suitable pots, followed by the number of flowers to place. This is followed by the location of each suitable pot.

Example Input

For example, the scenario described above would be encoded as follows:

5 3
1
2
8
4
9

Output

For each set of pots and flowers, determine the optimal minimum number of pots between each flower.

Example Output

For the scenario described above, the output would be:

2

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa19-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge03               # Create and checkout challenge03 branch

$ $EDITOR challenge03/program.cpp           # Edit your code

$ git add challenge03/program.cpp           # Stage your changes
$ git commit -m "challenge03: done"         # Commit your changes

$ git push -u origin challenge03            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge03 assignment ...
Submitting challenge03 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge03/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa19/challenge03
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 02 TA List to determine your corresponding TA for the merge request.