Злі корови (Золото)

Бесі придумала гру. Гравець кидає корову на одномірну сцену, що складається з багатьох стогів сіна, розташованих у різних точках числової прямої. Після приземлення корови може виникнути ланцюгова реакція вибухів. Мета - використовуючи одну корову, почати ланцюгову реакцію так, щоб підірвати всі стоги сіна.

Є n стогів сіна, розташованих у різних цілочисельних позиціях x[1], x[2], ..., x[n] на числовій прямій. Якщо корова приземлиться з енергією r у позиції x, це викличе вибух "радіусом r", що викличе вибухи всіх стогів сіна в діапазоні x − r ... x + r. Усі стоги сіна в цьому діапазоні також одночасно вибухають з радіусом вибуху r − 1. Усі ще не підірвані стоги сіна, що потрапили в цей діапазон, знову вибухають вже з радіусом вибуху r − 2, і так далі.

Визначте мінімальну кількість енергії r, з якою повинна приземлитися корова, так що якщо вона приземлиться в оптимальному положенні, то вибухнуть усі стоги сіна на сцені.

Вхідні дані

Перший рядок містить n (2 ≤ n ≤ 50000). Наступні n рядків містять цілі числа x[1] ... x[n] (кожне в діапазоні 0 ... 10^9).

Вихідні дані

Виведіть мінімальну енергію R, з якою повинна приземлитися корова, для того, щоб підірвати всі стоги сіна. Відповідь округлити і вивести з одним знаком після коми.

Приклади

Примітка

У цьому прикладі, корова приземлившись з енергією 3 у позиції 5, викличе вибухи стогів сіна в позиціях 3 і 8, потім вибухи будуть з радіусом 2, охоплюючи позиції 1 і 10, які викличуть вибухи радіусом 1, підриваючи останній стіг сіна в позиції 11, яка вибухає з радіусом 0.