410254: GYM103993 I Lanterns

Monocarp lives on a street which can be represented as a segment of the $$$oX$$$ axis. The street begins in point $$$0$$$ and ends in point $$$f$$$. There are $$$n$$$ pillars on the street, they are located in points $$$a_1, a_2, \dots, a_n$$$.

It is possible to install a lantern on each pillar. Each lantern illuminates a segment of the axis. If a lantern is installed on a pillar in point $$$x$$$, and the power of the lantern is $$$y$$$, then the segment from $$$x - y$$$ to $$$x + y$$$ (including both endpoints) will be illuminated.

Monocarp can install up to $$$k$$$ lanterns. Each lantern's power should be a positive integer.

Monocarp wants to illuminate the whole street, i. e. each point from $$$0$$$ to $$$f$$$. Note that all points from $$$0$$$ to $$$f$$$, including non-integer ones, should be illuminated.

To achieve this, Monocarp will choose $$$k$$$ pillars, install lanterns on them (one lantern on each of the chosen pillars), and tune all lanterns, so they have the same power, equal to $$$d$$$.

Monocarp doesn't want to spend too much money on electricity (the more power the lantern has, the more it consumes). Help him calculate the minimum possible power for his $$$k$$$ lanterns, so they can be installed in such a way that the whole street (from $$$0$$$ to $$$f$$$) is illuminated.

The first line contains three integers $$$n$$$, $$$k$$$ and $$$f$$$ ($$$1 \le k \le n \le 200\,000$$$, $$$1 \le f \le 10^{9}$$$) — the number of pillars, the number of lanterns and the rightmost point of the street, respectively.

The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le f$$$) — the locations of the lanterns. The elements of the sequence are pairwise distinct.

Print one integer — the minimum possible power of lanterns (all $$$k$$$ lanterns should have the same power) such that $$$k$$$ lanterns are enough to illuminate the whole street from the point $$$0$$$ to the point $$$f$$$ (including non-integer points).

2 1 12
6 4

6

4 2 20
3 6 13 19

7

2 2 1
0 1

1

2 1 1
0 1

1

10 4 100
34 52 12 35 89 60 77 43 23 11

15

In the first example, it is possible to install a lantern with power $$$6$$$ on a pillar in point $$$6$$$. Then all points from $$$0$$$ to $$$12$$$ will be illuminated.

In the second example, it is possible to install the lanterns in points $$$3$$$ and $$$13$$$ with power $$$7$$$. Then all points from $$$0$$$ to $$$20$$$ will be illuminated. Note that the lantern in point $$$3$$$ will illuminate the segment $$$[-4, 10]$$$, which is partially outside the street, but it doesn't make the placement incorrect.

In the third example, Monocarp has to install the lanterns on both pillars with power $$$1$$$, since all points (including non-integer ones) should be illuminated, and the power of the lanterns should be integer.

In the fourth example, the lantern with power $$$1$$$ can be installed on any pillar. All points from $$$0$$$ to $$$1$$$ will be illuminated.