Problem: You are given a sequence of n integers a1, a2, ..., an. 

Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - 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.

Input

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

The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

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

Examples

Input

3
1 2 3


Output

1.000000000000000


Input

4
1 2 3 4


Output

2.000000000000000


Input

10
1 10 2 9 3 8 4 7 5 6


Output

4.500000000000000

Note

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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
const double inf = 1e30;
struct point {
  int x, y;
  point() : x(0), y(0) {}
  point(int x_, int y_) : x(x_), y(y_) {}
  double get_b(double k) { return y - k * x; }
} a[maxn], b[maxn];
double get_k(point a, point b) { return 1.0 * (b.y - a.y) / (b.x - a.x); }
long long det(point a, point b) { return 1LL * a.x * b.y - 1LL * a.y * b.x; }
point operator-(point a, point b) { return point(a.x - b.x, a.y - b.y); }
int n, an, bn;
int main() {
  scanf("%d", &n);
  an = bn = 0, a[1] = b[1] = point(0, 0);
  for (int i = 1, v, s = 0; i <= n; ++i)
    scanf("%d", &v), a[i + 1] = b[i + 1] = point(i, s += v);
  for (int i = 1; i <= n + 1; ++i) {
    while (an >= 2 && det(a[an] - a[an - 1], a[i] - a[an - 1]) <= 0) --an;
    while (bn >= 2 && det(b[bn] - b[bn - 1], b[i] - b[bn - 1]) >= 0) --bn;
    a[++an] = a[i], b[++bn] = b[i];
  }
  double ans = inf, k1, k2;
  for (int i = 1, j = bn; i < an || j > 1;) {
    if (i < an)
      k1 = get_k(a[i], a[i + 1]);
    else
      k1 = inf;
    if (j > 1)
      k2 = get_k(b[j], b[j - 1]);
    else
      k2 = inf;
    if (k1 < k2)
      ans = min(ans, b[j].get_b(k1) - a[i++].get_b(k1));
    else
      ans = min(ans, b[j--].get_b(k2) - a[i].get_b(k2));
  }
  printf("%.12f\n", ans);
  return 0;
}