Гра в дорозі

Обмеження: 2 сек., 256 МіБ

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

Ось наприклад, є у вас послідовність з \(n\) цілих чисел \([a_1, a_2, \ldots, a_n]\). Назвемо слабкістю найбільше значення бідності серед усіх підвідрізків послідовності.

Бідність підвідрізка — це модуль суми його елементів.

Підвідрізок послідовності — це її неперервна підпослідовність.

Вам потрібно знайти таке дійсне число \(x\), що слабкість послідовності \([a_1-x, a_2-x, \ldots, a_n-x]\) буде мінімальною.

Допоможіть же собі, напишіть для цього програму.

Вхідні дані

Перший рядок містить ціле число \(n\) — довжину послідовності.

Другий рядок містить \(n\) цілих чисел \(a_i\) — елементи послідовності.

Вихідні дані

У єдиному рядку виведіть дійсне число — мінімальну можливу слабкість послідовності \([a_1-x, a_2-x, \ldots, a_n-x]\). Відповідь вважатиметься правильною, якщо її абсолютна чи відносна похибка не перевищуватиме \(10^{-4}\).

Обмеження

\(40 \%\) тестів: \(1 \le n \le 100, |a_i| \le 10^4\),

\(60 \%\) тестів: \(1 \le n \le 10^5, |a_i| \le 10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 4 -7 4	5.5

Примітки

У прикладі з умови при \(z=-1.5\) ми отримаємо послідовність \([5.5, -5.5, 5.5]\).

Бідності підвідрізків такі: [1; 1] — 5.5; [2;2] — |-5.5|=5.5; [3;3] — 5.5; [1;2] — |5.5-5.5|=0; [2;3] — |-5.5+5.5|=0; [1;3] — |5.5-5.5+5.5|=5.5.

Отже, слабкість отриманої послідовності дорівнює 5.5. Це найменша можлива слабкість.