Ліхтарики#513

Ліхтарики

2 secondes
256 mégaoctets
Medium

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

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

[x_i - r , x_i+r]

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

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

Input

Перший рядок містить одне ціле число (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) — проміжок, який потрібно освітити.

Output

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

Examples

Example 1

Loading
Loading