给定一个由 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,您的答案将被视为正确。
示例
输入 #1
3 1 2 3
输出 #1
1.000000000000000
输入 #2
4 1 2 3 4
输出 #2
2.000000000000000
输入 #3
10 1 10 2 9 3 8 4 7 5 6
输出 #3
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。