C. Слабость и бедность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность из n целых чисел a1, a2, ..., an.

Определите действительное число x, такое, чтобы слабость последовательности a1 - x, a2 - x, ..., an - x была как можно меньше.

Слабость последовательности определяется как максимальное значение бедности по всем отрезкам (непрерывным подпоследовательностям) последовательности.

Бедность отрезка определяется как модуль суммы элементов отрезка.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 200 000), длина последовательности.

Во второй строке записано n целых чисел a1, a2, ..., an (|ai| ≤ 10 000).

Выходные данные

Выведите действительное число, обозначающее минимально возможную слабость a1 - x, a2 - x, ..., an - x. Ответ будет засчитан, если его относительная или абсолютная погрешность не превышает 10 - 6.

Примеры
Входные данные
3
1 2 3
Выходные данные
1.000000000000000
Входные данные
4
1 2 3 4
Выходные данные
2.000000000000000
Входные данные
10
1 10 2 9 3 8 4 7 5 6
Выходные данные
4.500000000000000
Примечание

Для первого примера оптимальное значение x равняется 2, в таком случае последовательность примет вид  - 1, 0, 1 и максимальная бедность достигается либо на отрезке "-1", либо отрезке "1". Значение слабости (ответ) равняется в этом случае 1.

Во втором примере оптимальное значение x равняется 2.5, в таком случае последовательность принимает вид  - 1.5,  - 0.5, 0.5, 1.5, а максимальная бедность достигается либо на отрезке "-1.5 -0.5", либо на отрезке "0.5 1.5". Значение слабости (ответ) равняется в этом случае 2.