Вам дана последовательность из n целых чисел a1, a2, ..., an.
Определите действительное число x, такое, чтобы слабость последовательности a1 - x, a2 - x, ..., an - x была как можно меньше.
Слабость последовательности определяется как максимальное значение бедности по всем отрезкам (непрерывным подпоследовательностям) последовательности.
Бедность отрезка определяется как модуль суммы элементов отрезка.
Выходные данные
Выведите действительное число, обозначающее минимально возможную слабость a1 - x, a2 - x, ..., an - x. Ответ будет засчитан, если его относительная или абсолютная погрешность не превышает 10 - 6.
Примечание
Для первого примера оптимальное значение 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
1.000000000000000
|
|
2
|
4
1 2 3 4
|
2.000000000000000
|
|
3
|
10
1 10 2 9 3 8 4 7 5 6
|
4.500000000000000
|