Description

Every year the cows hold a peculiar hopscotch event, carefully jumping from one rock to another in a river. The competition is on a long straight river with a rock at the start and another rock at the end, which is $L$ units away from the start ($1 \le L\le 1,000,000,000$). Between the start and end rocks, there are $N$ additional rocks ($0\le N\le 50,000$), each at an integer distance $D_i$ from the start ($0<D_i<L$).

During the game, each cow starts from the start rock and tries to reach the end rock, only allowed to jump from one rock to another. Of course, the less agile cows will never reach the end rock and will eventually fall into the river.

Farmer John is proud of his cows and watches this contest every year. Over time, however, he has grown tired of watching timid cows from other farms hobble across short gaps between rocks. He plans to remove some rocks to increase the minimal distance the cows must jump to reach the end. He knows he cannot remove the start and end rocks, but he has enough resources to remove at most $M$ rocks ($0 \le M \le N$).

Before he starts removing rocks, FJ wants to know how much he can increase the minimal jump distance. Please determine, after optimally removing at most $M$ rocks, the maximum possible minimal distance that any cow must jump.

Formal statement: Given $N$ points on a line, remove at most $M$ points so that the minimum distance between consecutive remaining points (including the start at $0$ and the end at $L$) is maximized.

Input Format

The first line contains three space-separated integers: $L$, $N$, and $M$.

Lines $2 \dots N+1$ each contain one integer, the distance of a rock from the start. No two rocks share the same position.

Output Format

Output a single integer, the maximum possible value of the minimal jump distance after removing at most $M$ rocks.

25 5 2
2
14
11
21
17

4

Hint

Before removing any rock, the shortest jump is a length-$2$ jump from $0$ (start) to $2$; after removing the rocks at $2$ and $14$, the required shortest jump is $4$ (from $17$ to $21$ or from $21$ to $25$).

Translated by ChatGPT 5