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.

Difficulty: HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
def max_sum(nums, shift):
	res = 0
	res_m = 0
	cur_sum = 0
	cur_m_sum = 0
	for i in range(len(nums)):
		cur_sum += nums[i] + shift
		cur_m_sum += nums[i] + shift
		res = max(res, cur_sum)
		cur_sum = max(0, cur_sum)
		res_m = min(res_m, cur_m_sum)
		cur_m_sum = min(0, cur_m_sum)
	return (res, -res_m)

def weaks(nums, shift):
	return max_sum(nums, shift)

def main():
	int(input())
	nums = list(map(int, input().split()))
	l = -10000
	r = 10000
	ans = max(weaks(nums, 0))
	w1 = 1
	w2 = -1
	PREC = 10 ** (-6)
	while abs(w1 - w2) >= PREC and abs(w1 - w2) > PREC * max(w1, w2):
		m = (r + l) / 2
		(w1, w2) = weaks(nums, m)
		if w1 > w2:
			r = m
		else:
			l = m
	print((w1 + w2) / 2)
main()


def weakness(a, x):
	a = [elem - x for elem in a]
	acumulado = maximo = 0
	for elem in a:
		if acumulado + elem > 0:
			acumulado += elem
		else:
			acumulado = 0
		if acumulado > maximo:
			maximo = acumulado
	acumulado = minimo = 0
	for elem in a:
		if acumulado + elem < 0:
			acumulado += elem
		else:
			acumulado = 0
		if acumulado < minimo:
			minimo = acumulado
	return max(maximo, -minimo)
(n, a) = (input(), list(map(int, input().split())))
(inf, sup) = (min(a), max(a))
for _ in range(70):
	(c1, c2) = ((2 * inf + sup) / 3, (inf + 2 * sup) / 3)
	if weakness(a, c1) < weakness(a, c2):
		sup = c2
	else:
		inf = c1
print(weakness(a, (inf + sup) / 2))


n = int(input())
A = list(map(int, input().split()))

def f(A, x, sign=1):
	cur = 0
	mn = 0
	ans = -1 << 32
	if sign == 1:
		for y in A:
			cur += y - x
			ans = max(ans, cur - mn)
			mn = min(cur, mn)
	else:
		for y in A:
			cur -= y - x
			ans = max(ans, cur - mn)
			mn = min(cur, mn)
	return ans
(lo, hi) = (-10000, 10000)
nt = 100
while nt:
	nt -= 1
	mid = (lo + hi) / 2
	X = f(A, mid, sign=1)
	Y = f(A, mid, sign=-1)
	if X > Y:
		lo = mid
	else:
		hi = mid
print(abs(f(A, lo)))


def max_sum(x):
	ans = now = 0
	for v in a:
		now += v - x
		now = max(now, 0)
		ans = max(ans, now)
	return ans

def min_sum(x):
	ans = now = 0
	for v in a:
		now += v - x
		now = min(now, 0)
		ans = min(ans, now)
	return ans
n = int(input())
a = [int(x) for x in input().split()]
l = min(a)
r = max(a)
for _ in range(50):
	x = (r + l) / 2
	A = abs(max_sum(x))
	B = abs(min_sum(x))
	if A < B:
		r = x
	else:
		l = x
print(max(A, B))


from __future__ import division, print_function
import itertools
import sys
import os
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def is_it_local():
	script_dir = str(os.getcwd()).split('/')
	username = 'dipta007'
	return username in script_dir

def READ(fileName):
	if is_it_local():
		sys.stdin = open(f'./{fileName}', 'r')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if not is_it_local():
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def input1(type=int):
	return type(input())

def input2(type=int):
	[a, b] = list(map(type, input().split()))
	return (a, b)

def input3(type=int):
	[a, b, c] = list(map(type, input().split()))
	return (a, b, c)

def input_array(type=int):
	return list(map(type, input().split()))

def input_string():
	s = input()
	return list(s)
if is_it_local():

	def debug(*args):
		st = ''
		for arg in args:
			st += f'{arg} '
		print(st)
else:

	def debug(*args):
		pass
arr = []

def fun(x):
	cum = 0
	res = 0
	for v in arr:
		nw = v - x
		cum += nw
		cum = max(cum, 0)
		res = max(res, cum)
	cum = 0
	for v in arr:
		nw = -(v - x)
		cum += nw
		cum = max(cum, 0)
		res = max(res, cum)
	return res

def main():
	global arr
	n = input1()
	arr = input_array()
	low = -10000
	high = 10000
	loop = 100
	while loop > 0:
		loop -= 1
		m1 = (low * 2.0 + high) / 3.0
		m2 = (low + high * 2.0) / 3.0
		y1 = fun(m1)
		y2 = fun(m2)
		if y1 > y2:
			low = m1
		else:
			high = m2
	print(fun((low + high) / 2.0))
	pass
main()


n = int(input())
a = list(map(int, input().split()))

def f(x):
	(mx, cur) = (0, 0)
	for i in range(n):
		cur = max(cur, 0) + a[i] - x
		mx = max(mx, cur)
	cur = 0
	for i in range(n):
		cur = max(cur, 0) + x - a[i]
		mx = max(mx, cur)
	return mx
(L, R) = (min(a), max(a) + 1)
for t in range(100):
	d = (R - L) / 3
	(x1, x2) = (L + d, R - d)
	if f(x1) > f(x2):
		L = x1
	else:
		R = x2
print('{:.10f}'.format(f(L)))


def f(x):
	bi = 0
	ci = 0
	cnt1 = -10 ** 10
	minsum1 = 10 ** 10
	cnt2 = -10 ** 10
	minsum2 = 10 ** 10
	for i in range(len(A)):
		if bi - minsum1 > cnt1:
			cnt1 = bi - minsum1
		if bi <= minsum1:
			minsum1 = bi
		if ci - minsum2 > cnt2:
			cnt2 = ci - minsum2
		if ci <= minsum2:
			minsum2 = ci
		bi += A[i] - x
		ci += x - A[i]
	if bi - minsum1 > cnt1:
		cnt1 = bi - minsum1
	if bi <= minsum1:
		minsum1 = bi
	if ci - minsum2 > cnt2:
		cnt2 = ci - minsum2
	if ci <= minsum2:
		minsum2 = ci
	return max(cnt1, cnt2, 0)
n = int(input())
A = list(map(int, input().split()))
l = min(A)
r = max(A)
for _ in range(70):
	p = l + (r - l) / 3
	q = r - (r - l) / 3
	x = f(p)
	y = f(q)
	if x > y:
		l = p
	elif y > x:
		r = q
	else:
		l = p
		r = q
print(f(l))


import sys
n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]
eps = 1e-12

def f(x):
	mx = a[0] - x
	tsmx = 0.0
	mn = a[0] - x
	tsmn = 0.0
	for ai in a:
		tsmx = max(tsmx + ai - x, ai - x)
		mx = max(tsmx, mx)
		tsmn = min(tsmn + ai - x, ai - x)
		mn = min(tsmn, mn)
	return (abs(mx), abs(mn))
l = min(a)
r = max(a)
(f1, f2) = f(l)
for i in range(0, 90):
	m = (l + r) / 2
	(f1, f2) = f(m)
	if f1 > f2:
		l = m
	else:
		r = m
(A, B) = f(l)
print(min(A, B))


def cal(x, li, sign):
	sum = 0
	ans = 0
	for i in range(0, n):
		sum += (li[i] - x) * sign
		if sum < 0:
			sum = 0
		if sum > ans:
			ans = sum
	return ans
n = int(input())
li = [int(x) for x in input().split()]
r = max(li)
l = min(li)
ans = -1
mn = 99999999
for i in range(30):
	k = (r + l) / 2
	a1 = cal(k, li, 1)
	a2 = cal(k, li, -1)
	if abs(a1) < abs(a2):
		r = k
	else:
		l = k
	if abs(abs(a1) - abs(a2)) < mn:
		mn = abs(abs(a1) - abs(a2))
		ans = abs(a1)
		if abs(a2) > abs(a1):
			ans = abs(a1)
	if r - l < 1e-06:
		break
print(ans)


def main():
	input()
	a = list(map(int, input().split()))

	def f(a):
		maxend = maxnow = 0
		for x in a:
			maxend = max(0, maxend + x)
			maxnow = max(maxnow, maxend)
		return maxnow
	f1 = lambda x: f((i - x for i in a))
	f2 = lambda x: f((x - i for i in a))
	Max = max((abs(i) for i in a))
	(L, R) = (-Max, Max)
	eps = 10 ** (-8)
	for i in range(100):
		m = (L + R) / 2
		(v1, v2) = (f1(m), f2(m))
		if abs(v1 - v2) < eps:
			break
		if v1 > v2:
			L = m
		else:
			R = m
	print(v1)
main()


n = int(input())
A = list(map(int, input().split()))

def max_subarray(A):
	max_ending_here = max_so_far = 0
	for x in A:
		max_ending_here = max(0, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far

def f1(x):
	return max_subarray((a - x for a in A))

def f2(x):
	return max_subarray((-a + x for a in A))
m = max((abs(a) for a in A))
(l, r) = (-m, m)
for _ in range(100):
	mid = (l + r) / 2
	(v1, v2) = (f1(mid), f2(mid))
	if abs(v1 - v2) < 1e-08:
		break
	elif v1 > v2:
		l = mid
	else:
		r = mid
print(v1)