Codeforces Round #320 Div2 E / Div1 C

E.py

n = input()
d = list(map(int,raw_input().split(" ")))
s = d[:]
for i in range(len(d)):
	if(i>0):
		s[i] = s[i-1] + d[i]
l = min(d)
ll = l
r = max(d)
rr = r
step = 1.0

def weak(x):
	ss = [0] + [s[i] - x*(1+i) for i in range(len(s))]
	return max(ss) - min(ss)
t = True
x = 0
while(abs(ll-rr) > 10**(-6)):
	if t:
		k = l
	else:
		k = r
	x = k + step
	if(weak(x) < weak(k)):
		if t:
			l = x
		else:
			r = x
	else:
		if t:
			rr = x
			l = ll
		else:
			ll = x
			r = rr
		t = not t
		step *= -0.5
x = (ll+rr)/2.0

print weak(x)