G. Stores
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp lives in a city, which can be represented as a segment of the number line. The leftmost border of the city is at the point $$$0$$$, and the rightmost border is at the point $$$10^{9}$$$.

There are $$$n$$$ stores in the city. Each store is located at a point with integer coordinate: the $$$i$$$-th store is located at the point $$$a_i$$$. Among the $$$n$$$ stores, there is exactly one store at the point $$$0$$$ and exactly one store at the point $$$10^{9}$$$. There is at most one store at each integer coordinate.

The government has decided to build $$$m$$$ more stores in the city. It is prohibited to build a new store at a point where a store already exists, and at each integer point, at most one new store can be built. It is also prohibited to build stores to the left of point $$$0$$$ and to the right of point $$$10^{9}$$$.

Your task is to choose where to build the new $$$m$$$ stores in such a way that among all $$$(n+m-1)$$$ pairs of neighboring stores, the maximum distance between the stores in a pair is the minimum possible. In other words, you have to minimize the length of the longest segment connecting two neighboring stores.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — the number of stores already built in the city and the number of new stores to be built.

The second line contains a sequence of distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the coordinate of the $$$i$$$-th store.

Additional constraint on the input: there is exactly one number $$$0$$$ (the store at coordinate $$$0$$$) and exactly one number $$$10^{9}$$$ (the store at coordinate $$$10^{9}$$$) in the given sequence.

Output

Print one integer — the minimum possible maximum distance between two neighboring stores.

Examples
Input
4 1
750000000 250000000 0 1000000000
Output
250000000
Input
2 2
0 1000000000
Output
333333334
Input
3 17
500000000 0 1000000000
Output
55555556
Input
4 2000
333333333 0 777777777 1000000000
Output
499376
Note

In the first example, a new store needs to be built at point $$$500\,000\,000$$$. Then the distance between all pairs of neighboring stores will be $$$250\,000\,000$$$.

In the second example, two new stores can be built at points $$$333\,333\,333$$$ and $$$666\,666\,666$$$. Then the stores will be located at points $$$[0, 333\,333\,333, 666\,666\,666, 1\,000\,000\,000]$$$, and the maximum distance between a pair of neighboring stores will be $$$1\,000\,000\,000 - 666\,666\,666 = 333\,333\,334$$$ (between the third and fourth stores).