Ліхтарики#513

Ліхтарики

2 секунди
256 мегабайтів
Середня

На числовій прямій є ліхтариків, які розташовані в точках x_1, x_2, x_3, x_4, \dots, x_n.

Кожен ліхтарик має однаковий радіус освітлення та освітлює:

[x_i - r , x_i+r]

Тобто, ліхтарик освітлює всі точки, які знаходяться на відстані не більше , включно з точками, які знаходяться на відстані рівно .

Вам потрібно знайти мінімальний радіус освітлення, який потрібен, щоб всі точки на відрізку (не лише цілочисельні) на цьому проміжку були освітлені.

Вхідні дані

Перший рядок містить одне ціле число (1 \le n \le 10^6) — кількість ліхтариків.

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — координати ліхтариків.

Третій рядок містить два цілі числа та (1 \le L < R \le 10^9) — проміжок, який потрібно освітити.

Вихідні дані

Вивести мінімальний радіус, який потрібен для освітлення всього проміжку.

Приклади

Приклад 1

Loading
Loading