Description

The annual "Jumping Stones" competition is about to begin.

The competition takes place in a straight river channel where some huge rocks are distributed. The organizing committee has chosen two rocks as the start and the finish. Between the start and the finish, there are $N$ rocks (excluding the start and finish rocks). During the competition, participants start from the start rock and jump to an adjacent rock at each step until they reach the finish.

To increase the difficulty, the committee plans to remove some rocks so that the minimum jump distance during the competition is as large as possible. Due to budget limits, the committee can remove at most $M$ rocks between the start and the finish (the start and finish rocks cannot be removed).

Input Format

The first line contains three integers $L, N, M$, representing the distance from the start to the finish, the number of rocks between the start and the finish, and the maximum number of rocks the committee may remove, respectively. It is guaranteed that $L \geq 1$ and $N \geq M \geq 0$.

The next $N$ lines each contain one integer. On the $i$-th line, the integer $D_i\,(0 < D_i < L)$ denotes the distance from the start to the $i$-th rock. These rocks are given in increasing order of distance from the start, and no two rocks are at the same position.

Output Format

Output a single integer, which is the maximum possible minimum jump distance.

25 5 2 
2
11
14
17 
21

4

Hint

Explanation for Sample Input/Output 1

After removing the two rocks at distances $2$ and $14$ from the start, the minimum jump distance becomes $4$ (either when jumping from the rock at distance $17$ to the rock at distance $21$, or from the rock at distance $21$ to the finish).

Constraints

• For $20\%$ of the testdata, $0 \le M \le N \le 10$.
• For $50\%$ of the testdata, $0 \le M \le N \le 100$.
• For $100\%$ of the testdata, $0 \le M \le N \le 50000$, $1 \le L \le 10^9$.

Translated by ChatGPT 5