10
-405 -230 252 -393 -390 -259 97 163 81 -129
 3
10000 -10000 10000
 1
-10000
 20
-16 -23 29 44 -40 -50 -41 34 -38 30 -12 28 -44 -49 15 50 -28 38 -2 0

702.333333333333712
 10000.000000000016371
 0.000000000000000
 113.875000000000043

eps = 1e-6

def within_eps(x1, x2):
    if abs(x1 - x2) <= eps:
        return True
    return False

def ternary(fn, start, end):
    # print 'x1: %s' % x1
    # print 'x2: %s' % x2
    if start >= end:
        return None

    x1 = start + ((1.0/3.0) * (end - start))
    x2 = start + ((2.0/3.0) * (end - start))

    if fn(x1) == fn(x2):
        # print 'fn(%s) = %s' % (x1, fn(x1))
        # print 'fn(%s) = %s' % (x2, fn(x2))
        if within_eps(x1, x2):
            return x1
        else:
            return ternary(fn, x1, x2)
        return x1
    elif (fn(x1) < fn(x2)):
        # print 'fn(%s) = %s' % (x1, fn(x1))
        # print 'fn(%s) = %s' % (x2, fn(x2))
        return ternary(fn, start, x2)
    elif (fn(x1) > fn(x2)):
        # print 'fn(%s) = %s' % (x1, fn(x1))
        # print 'fn(%s) = %s' % (x2, fn(x2))
        return ternary(fn, x1, end)


def min_weakness(nums):
    def fn(x1):
        return weakness(nums, x1)
    x = ternary(fn, min(nums), max(nums))
    if x is None:
        return None
    return weakness(nums, x)

def weakness(nums, x):
    numbers = map(lambda a: a-x, nums)
    # print 'numbers; %s' % numbers
    max_all = None
    weakness_so_far = 0
    for i, n in enumerate(numbers):
        if weakness_so_far == 0:
            weakness_so_far = n
        elif weakness_so_far < 0:
            if n < 0:
                weakness_so_far += n
            elif n > 0:
                if max_all is None:
                    max_all = abs(weakness_so_far)
                elif abs(weakness_so_far) > max_all:
                    max_all = abs(weakness_so_far)
                weakness_so_far = n
        elif weakness_so_far > 0:
            if n > 0:
                weakness_so_far += n
            elif n < 0:
                if max_all is None:
                    max_all = weakness_so_far
                elif weakness_so_far > max_all:
                    max_all = weakness_so_far
                weakness_so_far = n
    if max_all is None:
        max_all = weakness_so_far
    else:
        max_all = max([max_all, weakness_so_far])
    # print 'max_all: %s' % abs(max_all)
    return abs(max_all)

# print weakness([1,2,3], 2)
# print weakness([1,2,3,4], 2.5)
print min_weakness([1,2,3])
print min_weakness([1,2,3,4])
"""
print weakness([1,2,3,4], 1)
print weakness([1,2,3,4], 1.5)
print weakness([1,2,3,4], 2)
print weakness([1,2,3,4], 2.5)
print weakness([1,2,3,4], 3)
print weakness([1,2,3,4], 3.5)
print weakness([1,2,3,4], 4)
"""
