Building Rest Stops

Dasom operates a toll highway of length L. There are currently N rest stops on the highway, and each position is given as its distance from the start of the highway. Dasom wants to build M more rest stops.

A new rest stop cannot be built at an existing rest stop, at the start of the highway, or at the end of the highway. Rest stops can only be built at integer positions.

The start and end of the highway are also treated as boundaries of sections without rest stops. After building exactly all M new rest stops, Dasom wants to make the maximum length of any continuous section without a rest stop as small as possible. Find that minimum possible value.

Consider a highway of length 1000 with existing rest stops at {200, 701, 800}, and suppose one more rest stop will be built. At first, the longest section without a rest stop is from 200 to 701, with length 501. If the new rest stop is built at position 451, the longest section length becomes 251, and it cannot be made smaller.

The first line contains three integers N, M, and L: the number of existing rest stops, the number of new rest stops to build, and the length of the highway.

The second line contains the positions of the existing rest stops, separated by spaces. If N = 0, the second line may be empty.

Print the minimum possible value of the maximum length of a section without a rest stop after building all M new rest stops.

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ position of each rest stop ≤ L - 1
• N + M < L
• All existing rest stop positions are distinct.
• Every number in the input is an integer.