The annual "Stone Jumping" competition is about to begin!
This competition takes place along a straight river channel, where several large rocks are scattered. The organizing committee has already selected two rocks as the starting point and the finishing point. Between the start and the finish, there are $N$ rocks (excluding the start and finish rocks). During the competition, contestants start from the starting point and jump to adjacent rocks step by step until they reach the finishing point.
To increase the difficulty of the competition, the committee plans to remove some rocks so that the shortest jump distance during the competition is as long as possible. Due to budget constraints, the committee can remove at most $M$ rocks between the start and the finish (the starting and finishing rocks cannot be removed).
Input
The first line contains three integers $L$, $N$, and $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 can remove, respectively.
The next $N$ lines each contain one integer. The $i$-th line contains $D_i$ ($0 < D_i < L$), representing the distance of the $i$-th rock from the starting point. These rocks are given in order of increasing distance from the starting point, and no two rocks appear at the same position.
Output
The output file contains only one integer, which is the maximum possible value of the shortest jump distance.
Examples
Input 1
25 5 2 2 11 14 17 21
Output 1
4
Note 1
If the two rocks at distances 2 and 14 from the start are removed, the shortest jump distance is 4 (jumping from the rock at distance 17 to the rock at distance 21, or from the rock at distance 21 to the finish).
Input 2
(See stone/stone2.in in the contestant directory)
Output 2
(See stone/stone2.ans in the contestant directory)
Constraints
For 20% of the data, $0 \le M \le N \le 10$.
For 50% of the data, $0 \le M \le N \le 100$.
For 100% of the data, $0 \le M \le N \le 50,000$, $1 \le L \le 1,000,000,000$.