Problem Description

At a sports meet, Xiaoming starts a standing long jump from the origin on the number line and jumps in the positive direction. The event has $n$ checkpoints $a_1, a_2, \cdots, a_n$, and $a_i \ge a_{i-1} > 0$. Xiaoming must jump to each checkpoint in order, and he can only land on checkpoints. Also, Xiaoming may add $m$ more checkpoints by himself to make the jumps easier.

Before the sports meet, Xiaoming makes a training plan so that the maximum distance of a single jump reaches $L$, and he also learns a burst skill that can be used once during the event. When he uses it, the maximum distance for that jump becomes $2L$. Xiaoming wants to know: what is the minimum value of $L$ that allows him to complete the event?

Input Format

The input has $2$ lines.

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ separated by spaces.

Output Format

Output $1$ line containing one integer, which is the answer.

5 3
1 3 5 16 21

3

Hint

[Sample Explanation]

Add checkpoints $10, 13, 19$. Then the jump distances are $1, 2, 2, 5, 3, 3, 3, 2$. Use the skill on the third jump.

[Constraints]

For $20\%$ of the testdata, $n \le 10^2$, $m \le 10^3$, $a_i \le 10^3$.
For $100\%$ of the testdata, $2 \le n \le 10^5$, $m \le 10^8$, $0 < a_i \le 10^8$.

Translated by ChatGPT 5