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;
double EPS = 1e-9;
int INF = 0x7FFFFFFF;
long long INFF = 0x7FFFFFFFFFFFFFFF;
double PI = acos(-1.0);
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};
inline void scanf(int &d1) { scanf("%d", &d1); }
inline void scanf(int &d1, int &d2) { scanf("%d%d", &d1, &d2); }
inline void scanf(int &d1, int &d2, int &d3) { scanf("%d%d%d", &d1, &d2, &d3); }
inline void scanf(long long &d1) { scanf("%I64d", &d1); }
inline void scanf(long long &d1, long long &d2) {
  scanf("%I64d%I64d", &d1, &d2);
}
inline void scanf(long long &d1, long long &d2, long long &d3) {
  scanf("%I64d%I64d%I64d", &d1, &d2, &d3);
}
inline void scanf(char *temp) { scanf("%s", temp); }
inline void printf(int d1) { printf("%d\n", d1); }
inline void printf(int d1, int d2) { printf("%d %d\n", d1, d2); }
inline void printf(double f1) { printf("%.17g\n", f1); }
inline void printf(long long l1) { printf("%I64d\n", l1); }
inline void printf(long long l1, long long l2) {
  printf("%I64d %I64d\n", l1, l2);
}
inline string tostring(int a) {
  char x[100];
  sprintf(x, "%d", a);
  string s = x;
  return s;
}
inline void toupperstring(string &s) {
  for (int(i) = (0); (i) < ((int)s.size()); ++(i)) {
    if (s[i] >= 'a' && s[i] <= 'z') {
      s[i] = s[i] - 'a' + 'A';
    }
  }
}
inline void tolowerstring(string &s) {
  for (int(i) = (0); (i) < ((int)s.size()); ++(i)) {
    if (s[i] >= 'A' && s[i] <= 'Z') {
      s[i] = s[i] - 'A' + 'a';
    }
  }
}
inline int toint(string a) {
  char x[100];
  int res;
  strcpy(x, a.c_str());
  sscanf(x, "%d", &res);
  return res;
}
inline void gopen(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
inline void gcase(int id) { printf("Case #%d:", id); }
template <typename T1, typename T2, typename T>
inline typename T::iterator findorinsert(T &m, const T1 &t1, const T2 &t2) {
  typename T::iterator iter = m.find(t1);
  if (iter == m.end()) {
    m.insert(make_pair(t1, t2));
    return m.find(t1);
  } else {
    return iter;
  }
}
template <typename T>
inline T gcd(T u, T v) {
  while (v != 0) {
    T r = u % v;
    u = v;
    v = r;
  }
  return u;
}
template <typename T, int n>
struct Vector {
  T data[n];
  void read() {
    for (int(i) = (0); (i) < (n); ++(i)) {
      cin >> data[i];
    }
  }
  inline T operator*(const Vector<T, n> &v) const {
    T res = 0;
    for (int(i) = (0); (i) < (n); ++(i)) {
      res += data[i] * v[i];
    }
    return res;
  }
  inline bool operator<(const Vector<T, n> &v) const {
    for (int(i) = (0); (i) < (n); ++(i)) {
      if (data[i] != v[i]) {
        return data[i] < v[i];
      }
    }
    return false;
  }
  inline bool operator==(const Vector<T, n> &v) const {
    for (int(i) = (0); (i) < (n); ++(i)) {
      if (data[i] != v[i]) {
        return false;
      }
    }
    return true;
  }
  inline T &operator[](int id) { return data[id]; }
  inline T operator[](int id) const { return data[id]; }
  inline int size() const { return n; }
};
template <typename T>
inline Vector<T, 2> make_vector(const T &t1, const T &t2) {
  Vector<T, 2> res = {t1, t2};
  return res;
}
template <typename T, int n>
struct Matrix {
  Vector<T, n> data[n];
  inline Vector<T, n> operator*(const Vector<T, n> &v) const {
    Vector<T, n> res;
    for (int(i) = (0); (i) < (n); ++(i)) {
      res[i] = data[i] * v;
    }
    return res;
  }
  inline Matrix<T, n> operator*(const Matrix<T, n> &m) const {
    Matrix<T, n> res;
    for (int(i) = (0); (i) < (n); ++(i)) {
      Vector<T, n> temp;
      for (int(j) = (0); (j) < (n); ++(j)) {
        temp[j] = m[j][i];
      }
      for (int(j) = (0); (j) < (n); ++(j)) {
        res[j][i] = data[j] * temp;
      }
    }
    return res;
  }
  static inline Matrix<T, n> identity() {
    Matrix<T, n> res;
    for (int(i) = (0); (i) < (n); ++(i)) {
      memset(res[i].data, 0, sizeof(T) * n);
    }
    for (int(i) = (0); (i) < (n); ++(i)) {
      res[i][i] = 1;
    }
    return res;
  }
  Vector<T, n> &operator[](int id) { return data[id]; }
  Vector<T, n> operator[](int id) const { return data[id]; }
  int size() const { return n; }
};
template <typename T, int n>
class BIT {
 public:
  BIT(int size = n) {
    memset(bit, 0, sizeof(bit));
    this->size = size;
  }
  BIT(T *data, int size = n) {
    this->size = size;
    for (int i = 1; i <= size; i++) {
      bit[i] = data[i - 1];
      for (int j = i - 1; j > i - lowbit(i); j--) {
        bit[i] += bit[j];
      }
    }
  }
  void edit(int i, T delta) {
    for (int j = i + 1; j <= size; j += lowbit(j)) {
      bit[j] += delta;
    }
  }
  T sum(int k) {
    T ans = 0;
    for (int i = k + 1; i > 0; i -= lowbit(i)) {
      ans += bit[i];
    }
    return ans;
  }

 private:
  T bit[n + 1];
  int size;
  inline int lowbit(int x) const { return x & (-x); }
};
class Prime {
 public:
  Prime(int num) {
    bits.resize(num + 1, true);
    sieve();
    collect();
  }
  bool is_prime(int num) const { return bits[num]; }
  int find1factor(int num) const {
    for (int(i) = (0); (i) < ((int)results.size()); ++(i)) {
      if (num % results[i] == 0) {
        return results[i];
      }
    }
    return num;
  }

 private:
  vector<bool> bits;
  vector<int> results;
  void sieve() {
    bits[0] = false;
    bits[1] = false;
    for (int i = 2; i < (int)bits.size(); ++i) {
      if (bits[i] == true) {
        for (int j = 2;; ++j) {
          int v2 = j * i;
          if (v2 >= (int)bits.size()) {
            break;
          }
          bits[v2] = false;
        }
      }
    }
  }
  void collect() {
    for (int i = 0; i < (int)bits.size(); ++i) {
      if (bits[i]) {
        results.push_back(i);
      }
    }
  }
};
template <int n, int m>
struct Graph {
  int head[n], edge_id;
  struct {
    int to, next;
  } edges[m];
  void init(int num = n) {
    edge_id = 0;
    memset(head, -1, sizeof(int) * num);
  }
  int add(int from, int to) {
    edges[edge_id].next = head[from];
    edges[edge_id].to = to;
    head[from] = edge_id;
    edge_id++;
    return head[from];
  }
  inline int next(int edge) const { return edges[edge].next; }
  inline int to(int edge) const { return edges[edge].to; }
};
template <class T>
inline void hash_combine(std::size_t &seed, const T &v) {
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <typename T, int n>
struct VectorHash {
  inline std::size_t operator()(const Vector<T, n> &v) const {
    std::size_t seed = 0;
    for (int(i) = (0); (i) < (n); ++(i)) {
      hash_combine(seed, v[i]);
    }
    return seed;
  }
};
const int max_n = 200000;
int a[max_n];
double b[max_n];
int n;
double maxSum(double A[]) {
  double ans = 0, tmp = 0;
  for (int i = 0; i < n; i++) {
    tmp += A[i];
    if (tmp < 0) tmp = 0;
    ans = max(ans, tmp);
  }
  return ans;
}
double calc(double x) {
  for (int i = 0; i < n; i++) b[i] = a[i] - x;
  double ans1 = maxSum(b);
  for (int i = 0; i < n; i++) b[i] = -b[i];
  double ans2 = maxSum(b);
  return max(ans1, ans2);
}
int main() {
  double vmax = -INF, vmin = INF;
  scanf(n);
  for (int(i) = (0); (i) < (n); ++(i)) {
    scanf(a[i]);
    vmax = max(vmax, (double)a[i]);
    vmin = min(vmin, (double)a[i]);
  }
  double v1, v2, c1, c2;
  while (true) {
    v1 = (2 * vmin + vmax) / 3;
    v2 = (vmin + 2 * vmax) / 3;
    c1 = calc(v1);
    c2 = calc(v2);
    if (c1 < c2) {
      vmax = v2;
    } else {
      vmin = v1;
    }
    if (abs(vmax - vmin) < 1e-11) {
      break;
    }
  }
  printf(c1);
  return 0;
}