During these difficult Covid times, it is important to balance getting fresh air and maintaining social distancing standards to keep everyone safe. You work for the local government and help run a local park. You want your park visitors to be as happy and safe as possible. You have picnic tables at the park and many visitors arriving. Your job is to assign picnic tables to your visitors to try and spread the visitors out as much as possible (each visitor must hang out at one of the tables).

Your park is very peculiar. It is a very long, narrow park. The picnic tables are spread out in a straight line through this long narrow park, and the distance between picnic tables varies (they are not uniformly positioned across the park). In addition, the tables are WAY too heavy to move. Given a list of the positions of the picnic tables in the park, and the number of visitors that wish to use the park, return the maximum social distancing value that can be achieved by assigning visitors to tables. By maximum, we mean the arrangement of visitors that maximizes the distance between the closest two patrons in the park.

Input

The input file will begin with one line containing n ≤ 106 and p ≤ 106, the number of picnic tables in your park and the number of visitors respectively. The following n lines will each contain a single integer li ≤ 108 describing the integer position of table i. These positions will be sorted in increasing order. All positions will be unique.

Output

Output the largest possible value of the minimum distance between visitors after being seated in the optimal arrangement at the picnic tables.

Sample Input

5 3

1

2

4

8

9

Sample Output

3

This assignment has been answered 3 times in private sessions.