F. Incubation Line
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eggward is working on a hobby project and recently acquired $$$n$$$ eggs that he wants to try and hatch that are stuck at fixed positions along a number line. He has some heat lamps, and he wants to keep the eggs close to the heat lamps in order to ensure they receive the warmth they need. Unfortunately, he only has $$$k$$$ heat lamps to incubate these eggs with. His goal is to minimize the maximum distance from any egg to its nearest heat lamp. Help him find this distance. The lamps are hung above the eggs so they can be at the same position on the number line, and all lamps must be at integer positions.

Input

The first line will contain two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — the number of eggs and the number of heat lamps respectively.

The following line will contain $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) indicating the position of the $$$i^{\text{th}}$$$ egg. Furthermore, the $$$a_i$$$ are guaranteed to be distinct, that is, if $$$i \neq j$$$, then $$$a_i \neq a_j$$$.

Output

Output one integer indicating the minimal possible max distance from any egg to its nearest heat lamp.

Examples
Input
3 2
0 5 7
Output
1
Input
5 2
-2 1 0 -1 4
Output
2
Note

Sample 1 Explanation: We can place one heat lamp at 0, and another at 6. The distance from the 0 egg to its nearest lamp is 0. The distance from the 5 and 7 eggs to their nearest lamp is 1. Thus, the minimum max distance we can achieve is 1.

Sample 2 Explanation: We can place one heat lamp at 0, and one heat lamp at 2. Then every egg is at most 2 away from the nearest lamp.