You are given a sequence of n integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 

Determine a real number *x* such that the weakness of the sequence *a*<sub class="lower-index">1</sub> - *x*, *a*<sub class="lower-index">2</sub> - *x*, ..., *a*<sub class="lower-index">*n*</sub> - *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.
The first line contains one integer *n* (1 ≤ *n* ≤ 200 000), the length of a sequence.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (|*a*<sub class="lower-index">*i*</sub>| ≤ 10 000).
def maxabssum(a):
    r = v = a[0]
    for i in range(1, len(a)):
        if (v < 0):
            v = 0
        v += a[i]
        r = max(r, v)
    return r

def poorness(a):
    return max(maxabssum(a), maxabssum([-x for x in a]))

def main():
    eps = 1e-8

    n = int(input())
    a = [int(x) for x in input().split(' ')]

    l = -20000
    r = 20000
    for i in range(1000):
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3
        k1 = poorness([x-m1 for x in a])
        k2 = poorness([x-m2 for x in a])
        #print('Round ' + str(i) + ': k1 = ' + str(k1) + '    k2 = ' + str(k2))
        if abs(k1-k2) < eps:
            break
        if k1 < k2:
            r = m2
        else:
            l = m1
    #print(str(l) + ' ' + str(r) + ' ' + str(m1) + ' ' + str(m2))
    print(poorness([x-l for x in a]))

main()
