Maximum Minimum Jump Distance

In the annual "Jumping Stones" competition a straight river is used with several huge rocks scattered along it. The organizing committee has fixed two special rocks as the start and the end. Between these two, there are N rocks (excluding the start and end rocks). In the competition, players must jump from one rock to the next (in order along the river) until reaching the end.

To increase the challenge, the committee is allowed to remove at most M of the N rocks (the start and end rocks cannot be removed) so that the minimum jump distance among consecutive rocks becomes as large as possible.

If we denote the positions of the rocks along the river (in increasing order) by \(a_0, a_1, \ldots, a_{N+1}\) (with \(a_0=0\) and \(a_{N+1}=L\)), then after removal the remaining positions will be \(b_0, b_1, \ldots, b_k\). The goal is to maximize the value of

\(\min_{0 \le i < k} \left(b_{i+1} - b_i\right)\).

inputFormat

The first line contains three positive integers separated by spaces: L (the length of the river), N (the number of rocks between the start and the end), and M (the maximum number of rocks that can be removed).

The following N lines each contain a single integer representing the position of a rock along the river. It is guaranteed that \(0 < \text{position} < L\) and all positions are distinct.

outputFormat

Output a single integer: the maximum possible value of the minimum jump distance after removing at most M rocks.

sample

25 5 2
2
11
14
17
21

4