CF578C.Weakness and Poorness

You are given a sequence of n integers _a_1, _a_2, ..., a__n.

Determine a real number x such that the weakness of the sequence _a_1 - x, _a_2 - x, ..., a__n - x is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.

给你一个由 $ n $ 个整数组成的序列 $ a_1,,a_2,,\dots,,a_n $。

请确定一个实数 $ x $，使得序列 $ a_1 - x,,a_2 - x,,\dots,,a_n - x $ 的“弱点”（weakness）尽可能小。

序列的弱点定义为该序列所有子段（即连续子序列）的“贫乏度”（poorness）的最大值。

子段的贫乏度定义为该子段中所有元素之和的绝对值。

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers _a_1, _a_2, ..., a__n (|a__i| ≤ 10 000).

第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$），表示序列的长度。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$|a_i| \leq 10\,000$）。

Output a real number denoting the minimum possible weakness of _a_1 - x, _a_2 - x, ..., a__n - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

输出一个实数，表示序列 $a_1 - x,\, a_2 - x,\, \dots,\, a_n - x$ 的最小可能弱点值。若你的答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case.

For the second sample the optimal value of x is 2.5 so the sequence becomes  - 1.5,  - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.

对于第一种情况，$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$。