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 ternary_search(nums, x):
    # get min sum
    sum, max_sum = 0, 0
    for i in range(len(nums)):
        if sum < 0:
            sum = 0
        sum += nums[i] - x
        max_sum = max(max_sum, sum)

    # get max sum
    sum = 0
    for i in range(len(nums)):
        if sum > 0:
            sum = 0
        sum += nums[i] - x
        max_sum = max(max_sum, abs(sum))

    return max_sum


def weaknessPoorness_ternarySearch():
    n = int(input.readline())
    nums = list(map(int, input.readline().split()))

    lo = -10000
    hi = 10000
    for _ in range(200):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3

        if ternary_search(nums, m1) >= ternary_search(nums, m2):
            lo = m1
        else:
            hi = m2

    print(min(ternary_search(nums, lo),ternary_search(nums, hi)))


weaknessPoorness_ternarySearch()