Cow Hopscotch

Cows play a peculiar game of hopscotch on a straight river. The river has a rock at the start (position 0) and another at the end (position L). In between, there are N rocks located at positions \(D_i\) (with \(0 < D_i < L\)). Farmer John can remove at most M of these intermediate rocks (the starting and ending rocks must remain) in order to maximize the minimum distance between any two adjacent rocks. Formally, if the final sequence of rocks (after removing some) is \(x_0=0, x_1, x_2, \dots, x_{k-1}=L\), you need to choose removals so that the quantity

[ d = \min_{0 \le i < k-1} (x_{i+1}-x_i) ]

is maximized. Determine the largest possible value of \(d\) achievable.

inputFormat

The first line contains three integers: \(L\), \(N\) and \(M\), where \(L\) (\(1 \le L \le 10^9\)) is the total length of the river, \(N\) (\(0 \le N \le 50000\)) is the number of intermediate rocks, and \(M\) (\(0 \le M \le N\)) is the maximum number of rocks that can be removed. Each of the following \(N\) lines contains one integer \(D_i\) (with \(0 < D_i < L\)), representing the position of an intermediate rock.

Note that the starting position (0) and the ending position (L) are implicit and cannot be removed.

outputFormat

Output a single integer: the maximum possible minimum distance between consecutive rocks after removing at most \(M\) rocks optimally.

sample

25 5 2
2
11
14
17
21

4