I. Фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп живет на улице, которая расположена вдоль оси $$$oX$$$. Улица начинается в точке $$$0$$$ и заканчивается в точке $$$f$$$. Также на улице есть $$$n$$$ столбов, расположенных в различных точках $$$a_1, a_2, \dots, a_n$$$.

На каждый столб можно повесить фонарь, который будет освещать определенный участок улицы. Если столб, на который повесили фонарь, находится в точке $$$x$$$, а мощность фонаря равна $$$y$$$, то будет освещен участок улицы от точки $$$x - y$$$ до точки $$$x + y$$$, включительно.

У Монокарпа есть $$$k$$$ фонарей, причем каждый фонарь можно настроить на любую мощность. Обратите внимание, что мощность освещения фонаря должна быть целым положительным числом.

С помощью своих фонарей Монокарп хочет осветить всю улицу, то есть каждая точка от $$$0$$$ до $$$f$$$ должна быть освещена. Обратите внимание, что должны быть освещены все точки от $$$0$$$ до $$$f$$$, в том числе и нецелочисленные.

Для этого он выберет $$$k$$$ столбов, на которые повесит фонари (на каждый столб ровно по одному фонарю), а также настроит все фонари на одинаковую мощность $$$d$$$.

Монокарп хочет сэкономить на потреблении электроэнергии (ведь чем мощнее светит фонарь, тем больше электроэнергии ему необходимо), поэтому перед вами стоит задача определить минимальное значение мощности каждого фонаря, которого будет достаточно, чтобы с помощью $$$k$$$ фонарей были освещены все точки улицы от $$$0$$$ до $$$f$$$.

Входные данные

В первой строке следуют три целых числа $$$n$$$, $$$k$$$ и $$$f$$$ ($$$1 \le k \le n \le 200\,000$$$, $$$1 \le f \le 10^{9}$$$) — количество столбов, на которые можно повесить фонари, количество фонарей и самая правая точка улицы.

Во второй строке следует последовательность различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le f$$$) — точки, в которых расположены столбы.

Выходные данные

Выведите минимальное значение мощности каждого фонаря (каждый из $$$k$$$ фонарей Монокарп настроит на одинаковую мощность), которого будет достаточно, чтобы с помощью $$$k$$$ фонарей были освещены все точки улицы от $$$0$$$ до $$$f$$$ (в том числе и нецелочисленные).

Примеры
Входные данные
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
Примечание

В первом примере нужно повесить фонарь на столб в точке $$$6$$$, а его мощность должна быть равна $$$6$$$. Тогда все точки улицы от $$$0$$$ до $$$12$$$ будут освещены.

Во втором примере можно повесить фонари на столбы в точках $$$3$$$ и $$$13$$$, а мощность каждого фонаря установить равной $$$7$$$. Тогда все точки улицы от $$$0$$$ до $$$20$$$ будут освещены. Обратите внимание, что фонарь на столбе в точке $$$3$$$ будет освещать участок $$$[-4, 10]$$$, и это допустимо.

В третьем примере можно повесить фонари на оба столба, а мощность каждого должна быть равна $$$1$$$, так как должны быть освещены все точки улицы, в том числе и нецелочисленные, а мощность каждого фонаря должна быть целым числом.

В четвертом примере можно повесить фонарь на любой из столбов, установив мощность освещения равную $$$1$$$. Тогда все точки улицы от $$$0$$$ до $$$1$$$ будут освещены.