P10909 [Lanqiao Cup 2024 National B] Standing Long Jump

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?

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 $1$ line containing one integer, which is the answer.

**[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