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

#!/usr/bin/python3 is a shebang line.
# Usage: cat in | python3 script.py  > out.txt

import os
import sys
from collections import defaultdict, OrderedDict
import itertools
import fileinput
import argparse

parser = argparse.ArgumentParser()
parser.add_argument('--test', required=False, default=False, action='store_true')
config = parser.parse_args()

TEST_MODE = config.test

EXPECTED_TEST_OUTPUT = '''
Case #1: 2
Case #2: 0
Case #3: -1
Case #4: 3
Case #5: 6
Case #6: 5
Case #7: 502
'''.strip()

print_ = print
def print(*args): raise ValueError("DO NOT USE, use pr instead.")

def pr(*args):
    if TEST_MODE:
        print_(*args)

class LineFeed:
    def __init__(self):
        self.feed = iter(fileinput.input(files=[]))

    def line(self):
        line = self.maybe_line()
        if line is not None:
            return line
        else:
            raise ValueError("Unexpected end of input at line %d" % fileinput.lineno())

    def maybe_line(self):
        try:
            line = next(self.feed)
        except StopIteration:
            return None
        if line.endswith('\n'):
            return line[:-1]
        return line

    def maybe_line_lookahead(self):
        line = self.maybe_line()
        if line is not None:
            self.feed = itertools.chain([line], self.feed)
        return line

    def is_end(self):
        return self.maybe_line_lookahead() is None

    def expect_end(self):
        line = self.maybe_line()
        if line is not None:
            raise ValueError("Expected end of input at line %d got '%s'" % (fileinput.lineno(), line))

    def item(self, typ=int):
        return typ(self.line())

    def items(self, typ=int):
        return list(map(typ, self.line().split()))


def parse_single_case(f):
    return [f.item(), f.items()]


def itern_n(f, n):
    for e in range(n):
        yield parse_single_case(f)

def iter_while_input(f):
    while 1:
        if f.is_end():
            break
        yield parse_single_case(f)

def iter_first_is_num_cases(f):
    num_cases = f.item()
    yield from itern_n(f, num_cases)

def single_case(f):
    yield parse_single_case(f)

def case_iter():
    f = LineFeed()
    yield from single_case(f)
    f.expect_end()

# --------------------------------------------------------------

def find_minimax(nums, x):
    bmini = float('inf')
    bmaxi = float('-inf')
    mini = maxi = 0.
    cum = 0
    for e in nums:
        cum += e - x
        bmini = min(bmini, cum - maxi)
        bmaxi = max(bmaxi, cum - mini)
        mini = min(mini, cum)
        maxi = max(maxi, cum)
    return bmini, bmaxi

def solve(case):
    n, nums = case
    bounds = [float(min(nums)), float(max(nums))]
    while 1:
        x = (bounds[0] + bounds[1]) / 2
        bmini, bmaxi = find_minimax(nums, x)
        pr(x, abs(bmini), abs(bmaxi))
        if abs(bmini) - abs(bmaxi) < 1e-7:
            return (abs(bmini) + abs(bmaxi)) / 2.
        if abs(bmini) > abs(bmaxi):
            bounds[1] = x
        else:
            bounds[0] = x


def transform_res(case_id, res):
    """case_id starts from 0, res is the output of solve for this case."""
    return str(res)


# --------------------------------------------------------------
from time import perf_counter

tot_t = 0.

def solve_all():
    global tot_t
    for case_id, case in enumerate(case_iter()):
        tot_t -= perf_counter()
        case_out = transform_res(case_id, solve(case))
        tot_t += perf_counter()
        yield case_out


pr("--- TEST MODE ACTIVE ---")
solutions = []
for solution in solve_all():
    solutions.append(solution)
    pr("solution=(%s)" % solution)

output = '\n'.join(solutions)

if not TEST_MODE:
    print_(output)
else:
    pr("TOTAL_TIME:", tot_t)
    pr("OUTPUT MATCHES EXPECTED:", EXPECTED_TEST_OUTPUT == output)

