← 返回题目列表

Codeforces · 578/C

C. 弱点和贫穷

中文机器翻译题面 查看原题

给定一个由 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。