Злі корови (Золото)#10598
Корова Бессі розробила те, що, на її думку, стане наступною популярною відеогрою: "Angry Cows". Сюжет гри, який Бессі вважає повністю оригінальним, полягає в наступному: гравець запускає корову з рогатки в одновимірну сцену, яка складається з багатьох стогів сіна, розташованих у різних точках числової прямої. Корова приземляється з достатньою силою, щоб підірвати стоги сіна, що знаходяться в безпосередній близькості від місця її приземлення, що, у свою чергу, може запустити ланцюгову реакцію, яка спричиняє взрив додаткових стогів сіна. Мета гри — за допомогою однієї корови запустити ланцюгову реакцію, яка знищить усі стоги сіна.
На числовій прямій розташовано стогів сіна в різних цілочисельних точках x_1, x_2, \ldots, x_n. Якщо корову запускають із силою , і вона приземляється в точці , то утворюється взрив радіусом , який охоплює всі стоги сіна, розташовані всередині інтервалу [x - r, x + r]. Потім ці стоги сіна самі взриваються (усі одночасно), кожен із радіусом взриву r - 1. Усі ще не взірвані стоги сіна, що потрапили в зону цих взривів, потім також взриваються (усі одночасно) з радіусом взриву r - 2, і так далі.
Визначте мінімальну силу , з якою можна запустити одну корову так, щоб, приземлившись у відповідному місці, вона врешті-решт спричинила взрив кожного стогу сіна на сцені.
У першому рядку міститься ціле число n~(2 \le n \le 50000). У кожному з наступних рядків міститься ціле число x_i~(0 \le x_i \le 10^9), яке задає позицію одного зі стогів сіна на числовій прямій.
Виведіть мінімальну силу , з якою необхідно запустити корову, щоб підірвати всі стоги сіна. Відповідь слід округлити та вивести рівно з однією цифрою після десяткової крапки.
У цьому прикладі корова, запущена з силою , наприклад, у точку , миттєво підриває стоги сіна в точках та . Потім ці стоги взриваються одночасно, кожен із радіусом взриву , охоплюючи стоги в точках та . Потім ці стоги одночасно взриваються з радіусом , охоплюючи останній стіг у точці , який, у свою чергу, взривається з радіусом .
Приклад 1