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 = 'def f(x):\n    bi = 0\n    ci = 0\n    cnt1 = -10 ** 10\n    minsum1 = 10 ** 10\n    cnt2 = -10 ** 10\n    minsum2 = 10 ** 10\n    for i in range(len(A)):\n        if bi - minsum1 > cnt1:\n            cnt1 = bi - minsum1\n        if bi <= minsum1:\n            minsum1 = bi\n        if ci - minsum2 > cnt2:\n            cnt2 = ci - minsum2\n        if ci <= minsum2:\n            minsum2 = ci\n        bi += A[i] - x\n        ci += x - A[i]\n    if bi - minsum1 > cnt1:\n        cnt1 = bi - minsum1\n    if bi <= minsum1:\n        minsum1 = bi\n    if ci - minsum2 > cnt2:\n        cnt2 = ci - minsum2\n    if ci <= minsum2:\n        minsum2 = ci\n    return max(cnt1, cnt2, 0)\n\n\nn = int(input())\nA = list(map(int, input().split()))\nl = min(A)\nr = max(A)\nfor _ in range(70):\n    p = l + (r - l) / 3\n    q = r - (r - l) / 3\n    x = f(p)\n    y = f(q)\n    if x > y:\n        l = p\n    elif y > x:\n        r = q\n    else:\n        l = p\n        r = q\nprint(f(l))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13265