Description

Every year, the cows hold various special versions of hopscotch competitions, including jumping from one rock to another in a river. This thrilling event takes place in a long, straight river channel, with a rock at the starting point and another at the endpoint, which is L units away (1 ≤ L ≤ 1,000,000,000) from the start. Between the starting point and the endpoint, there are N (0 ≤ N ≤ 50,000) rocks, each located at a distance Di (0 < Di < L) from the starting point.

During the competition, the cows take turns starting from the beginning, attempting to reach the endpoint by jumping from one rock to another. Of course, less capable cows may not be able to achieve this goal.

Farmer John is proud of his cows and has watched this event year after year. However, over time, seeing the timid cows from other farms slowly making their way between closely spaced rocks, he has grown weary. He plans to remove some rocks to maximize the shortest possible jumping distance from the start to the endpoint. He can remove at most M (0 ≤ M ≤ N) rocks, excluding the starting and endpoint rocks.

Please help Farmer John determine the longest possible shortest jumping distance after removing these rocks.

Input Format

The first line contains three integers L, N, M, separated by single spaces.
The next N lines each contain an integer representing the distance of each rock from the starting point. The rocks are listed in order of increasing distance from the start, and no two rocks occupy the same position.

Output Format

An integer representing the longest possible shortest jumping distance.

25 5 2
2
11
14
17
21

4

Hint

After removing the two rocks located at positions 2 and 14, the shortest jump distance is 4 (either from 17 to 21 or from 21 to 25).