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.


-----Input-----

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).


-----Output-----

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}.


-----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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nn = int(sys.stdin.readline())\na = [int(x) for x in sys.stdin.readline().split()]\n\neps = 1e-12\n\ndef f(x):\n    mx = a[0] - x\n    tsmx = 0.0\n    mn = a[0] - x\n    tsmn = 0.0\n    for ai in a:\n        tsmx = max(tsmx + ai - x, ai - x)\n        mx = max(tsmx, mx)\n        tsmn = min(tsmn + ai - x, ai - x)\n        mn = min(tsmn, mn)\n\n    return abs(mx), abs(mn)\n\nl = min(a)\nr = max(a)\nf1, f2 = f(l)\nfor i in range(0, 90):\n    m = (l + r) / 2\n    f1, f2 = f(m)\n    if f1 > f2:\n        l = m\n    else:\n        r = m\n\nA, B = f(l)\nprint(min(A,B))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13225