Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
from bisect import bisect

N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
for c in range(2,N-1):
    b1 = bisect(cums[:c], cums[c]//2)
    b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
    pq_cands = []
    for i in (b1,b1-1):
        if not 0 < i < c: continue
        p = cums[i]
        q = cums[c] - cums[i]
        pq_cands.append((p,q))
    rs_cands = []
    for i in (b2,b2-1):
        if not c < i < N: continue
        r = cums[i] - cums[c]
        s = cums[-1] - cums[i]
        rs_cands.append((r,s))
    for p,q in pq_cands:
        for r,s in rs_cands:
            mn = min(p,q,r,s)
            mx = max(p,q,r,s)
            ans = min(ans, mx-mn)
print(ans)

# Example run
# Input:
-98031
-5
# Output:
-4995
def dif(A):
    A_num = list(map(sum,A))
    return max(A_num) - min(A_num)


from copy import deepcopy

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

B =[[],[],[],[]]

for i in range(n):
    if i <= 3:
        B[i].append(A[i])
    else:
        B_num = list(map(sum,B))
        B[B_num.index(min(B_num))].append(A[i])

flag = True

while flag:
    flag = False
    for i in range(4):
        if flag:
            break
        for j in B[i]:
            if flag:
                break
            for k in range(4):
                if flag:
                    break
                C = deepcopy(B)
                if k!=i:
                    C[i].remove(j)
                    C[k].append(j)
                    if dif(B) > dif(C):
                        B = C
                        flag = True

print(dif(B))



# Example run
# Input:
-126905272
28016
# Output:
0
from itertools import accumulate as ac
n=int(input())
s=list(ac(list(map(int,input().split()))))
c=0
d=2
f=s[-1]
k=f
for i in range(1,n-1):
    while s[i]>s[c]+s[c+1]:
        c+=1
    while s[i]+f>s[d]+s[d+1]:
        d+=1
    j=[s[c],s[i]-s[c],s[d]-s[i],f-s[d]]
    k=min(max(j)-min(j),k)
print(k)

# Example run
# Input:
-51
-6607
# Output:
-6607
N=int(input())
A=list(map(int,input().split()))

SUM=sum(A)

left=0
i=0
while left<SUM/4:
    left+=A[i]
    i+=1
    print(i,left)

right=0
j=N-1
while right<SUM/4:
    right+=A[j]
    j-=1
    print(j,right)


    
def middlecut(i,j):
    left=sum(A[:i])
    right=sum(A[j:])
    ANS=10**16

    for k in range(i,j):
        midle=sum(A[i:k])
        midri=sum(A[k:j])

        if ANS>max(left,right,midle,midri)-min(left,right,midle,midri):
            ANS=max(left,right,midle,midri)-min(left,right,midle,midri)

    return ANS


ANS=10**16
for l in range(max(0,i-6),min(N,i+6)):
    for m in range(max(0,j-6),min(N,j+6)):
        ANS=min(ANS,middlecut(l,m))

print(ANS)


# Example run
# Input:
-4
-94404
# Output:
10000000000000000
n = int(input())
ans = []
lis = list(map(int,input().split()))
num = sum(lis[:2]) - sum(lis[2:])
cou = n-1
for i in range(3,n-1):
  if abs(num) < abs(sum(lis[:i])-sum(lis[i:])):
    cou = i-1
    break
  else:
    num = sum(lis[:i])-sum(lis[i:])

li = lis[:cou]
n = len(li)
nu = sum(li[:1]) - sum(li[1:])
co = n-1
for i in range(1,n):
  if abs(nu) < abs(sum(li[:i])-sum(li[i:])):
    co = i-1
    break
  else:
    nu = sum(li[:i])-sum(li[i:])
ans.append(sum(li[:co]))
ans.append(sum(li[co:]))

l = lis[cou:]
n = len(l)
nm = sum(l[:1]) - sum(l[1:])
c = n-1
for i in range(1,n):
  if abs(nm) < abs(sum(l[:i])-sum(l[i:])):
    c = i-1
    break
  else:
    nm = sum(l[:i])-sum(l[i:])
ans.append(sum(l[:c]))
ans.append(sum(l[c:]))

  #print(lis[co:cou+c])
lisa = lis[co:cou+c]
numb = sum(lisa[:1]) - sum(lisa[1:])
coun = n-1
for i in range(2,n):
    #print(abs(numb), abs(sum(lisa[:i])-sum(lisa[i:])))
  if abs(numb) <= abs(sum(lisa[:i])-sum(lisa[i:])):
    coun = i-1
    break
  else:
    numb = sum(lisa[:i])-sum(lisa[i:])
ans[1] = sum(lisa[:coun])
ans[2] = sum(lisa[coun:])
  #print(lisa[:coun],lisa[coun:])
print(max(ans)-min(ans))

# Example run
# Input:
0
5354599
# Output:
5354599
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Accumulation:
    def __init__(self,X,accumfunc,init_val=0):
        self.X = X
        self.accumfunc = accumfunc

        N = len(X)
        v1 = [0] * (N+1)
        v1[0] = init_val

        for i in range(N):
            v1[i+1] = accumfunc(v1[i],X[i])

        self.v1 = v1
    
    # 0-index
    def query(self,l,r):
        return self.v1[r+1] - self.v1[l]
    
    def get_array(self):
        return self.v1

INF=10**20
def main():
    N=ii()
    A=list(mi())
    B = []
    for a in A:
        B.append(a*2)

    def add(x,y): return x+y

    acc = Accumulation(A,add)
    accB = Accumulation(B,add)

    vA = acc.get_array()
    vB = accB.get_array()

    ans = INF
    for j in range(N):
        i1 = bisect.bisect_left(vB,vA[j+1]) - 1 

        Q,P=0,INF
        for di in [-1,0,1]:
            if not 0<= i1+di < N: continue
            q,p = acc.query(i1+di+1,j), acc.query(0,i1+di)
            if abs(p-q) < abs(P-Q):
                Q,P = q,p

        S,R = 0,INF
        i2 = bisect.bisect_left(vB,vA[N]+vA[j+1]) - 1
        for di in [-1,0,1]:
            if not 0<= i2+di < N: continue
            s,r = acc.query(i2+di+1,N-1), acc.query(j+1,i2+di)
            if abs(s-r) < abs(S-R):
                S,R=s,r



        ans = min(ans,abs(max(P,Q,R,S) - min(P,Q,R,S)))


    print(ans)





if __name__ == "__main__":
    main()

# Example run
# Input:
-220533202
49968
# Output:
100000000000000000000
N = int(input())
A = [0] + list(map(int, input().split()))
for i in range(1, N + 1):
    A[i] += A[i - 1]


# print (A)

ans = 10 ** 9

#基準を求める
stan = A[N]//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)

stan = (A[N] + 3)//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while index < N and A[index] - A[prev_index] < stan:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while index < N + 1 and A[index] - A[prev_index] < stan:
                index += 1
                if index == N + 1:
                    break
            PQRS[j] = A[index - 1] - A[prev_index]
            index -= 1
            prev_index = index
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)


print (ans)

# Example run
# Input:
1
8030667
# Output:
8030667
def main():
    num = int(input())
    data = list(map(int, input().split()))

    l, c, r = 1, 2, 3
    P = sum(data[:l])
    Q = sum(data[l:c])
    R = sum(data[c:r])
    S = sum(data[r:])

    ans = max(P, Q, R, S) - min(P, Q, R, S)

    while c <= num-2:
        while True:
            if abs(P-Q) < abs((P+data[l])-(Q-data[l])):
                break

            if l == c-1:
                break

            P += data[l]
            Q -= data[l]
            l += 1

        while True:
            if abs(R-S) < abs((R+data[r])-(S-data[r])):
                break
            if r == num-1:
                break

            R += data[r]
            S -= data[r]
            r += 1

        ans = min(max(P,Q,R,S)- min(P,Q,R,S), ans)

        # centerについて調整
        Q += data[c]
        R -= data[c]
        c += 1

    print(ans)

if __name__ == '__main__':
    main()


# Example run
# Input:
-2540
-1836
# Output:
1836
n = int(input())
a = [int(item) for item in input().split()]

cumsum = [0] * n
for i in range(n):
  if i == 0:
    cumsum[0] = a[0]
  else:
    cumsum[i] = cumsum[i-1] + a[i]
    
l = 0
r = 2
ans = sum(a)
for i in range(2, n-1):
  while cumsum[i] - cumsum[l+1] > cumsum[l]:
    l += 1
  while cumsum[-1] - cumsum[r+1] > cumsum[r] - cumsum[i]:
    r += 1
  a = cumsum[l]
  b = cumsum[i] - cumsum[l]
  c = cumsum[r] - cumsum[i]
  d = cumsum[-1] - cumsum[r]
  
  ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

# Example run
# Input:
-12211339
-118998188
# Output:
-118998188
n = int(input())
a = [int(item) for item in input().split()]

cumsum = [0] * n
for i in range(n):
  if i == 0:
    cumsum[0] = a[0]
  else:
    cumsum[i] = cumsum[i-1] + a[i]
    
l = 0
r = 2
ans = sum(a)
for i in range(1, n-1):
  while cumsum[i] - cumsum[l+1] > cumsum[l]:
    l += 1
  while cumsum[-1] - cumsum[r+1] > cumsum[r] - cumsum[i]:
    r += 1
  a = cumsum[l]
  b = cumsum[i] - cumsum[l]
  c = cumsum[r] - cumsum[i]
  d = cumsum[-1] - cumsum[r]
  
  ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

# Example run
# Input:
-449705
-318594
# Output:
-318594
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,5)
for i in range(1, N):
	for j in range(i + 1, N):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			temp = max(P, Q, R, S) - min(P, Q, R, S)
			if temp < ans:
				ans = temp
print(ans)


# Example run
# Input:
0
-84521052
# Output:
100000
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
				if ind == N:
					break
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind < N:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

# Example run
# Input:
-2857
1431333
# Output:
1431333
N = int(input())
A = list(map(int,input().split()))
B,C,D,E = [],[],[],[]
b,c,d,e =0,0,0,0
ans =[]
for i in range(0,N-3):
    for j in range(i+1,N-2):
        for k in range(j+1,N-1):
            B = A[0:i+1]
            C = A[i+1:j+1]
            D = A[j+1:k+1]
            E = A[k+1:N]
            b =sum(B)
            c =sum(C)
            d =sum(D)
            e =sum(E)
            ans.append(abs(max(b,c,d,e)-min(b,c,d,e)))
print(min(ans))

# Example run
# Input:
11
112430
# Output:
112430
#!/usr/bin/env python
from itertools import accumulate as ac
N = int(input())
A = list(ac(map(int, input().split())))
l, r, t = 0, 2, A[-1]
c = t

for m in A[1:-2]:
    while t+m > A[r]+A[r+1]:
        r += 1
    while m > A[l]+A[l+1]:
        l += 1
    x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
    c = min(c,x[-1]-x[0])
print(c)


# Example run
# Input:
-1325982
57961
# Output:
57961
n = int(input())
a = list(map(int,input().split()))

ans = 1000000000000000000000000000000000000
pair = [0,0,0,0]
for i in range(n-3):
	for j in range(i,n-2):
		for k in range(j,n-1):
			p = sum(a[0:i+1])
			q = sum(a[i+1:j+1])
			r = sum(a[j+1:k+1])
			s = sum(a[k+1:n])
			M = max(p,q,r,s)
			m = min(p,q,r,s)
			if ans > M-m:
				ans =  M-m
				
			
		
	
print(ans)

# Example run
# Input:
-1
-3439167
# Output:
1000000000000000000000000000000000000
n = int(input())
A = tuple(map(int, input().split()))
B = [0]*len(A)
s = 0
for i,v in enumerate(A):
    s += v
    B[i] = s

def df(a,b):
    mint = B[b-1]
    pr = qs = 0
    for i in range(a+1,b):
        if a == 0:
            pr = B[i-1]
            qs = B[b-1]-B[i-1]
        else:
            pr = B[i-1]-B[a-1]
            qs = B[b-1]-B[i-1]
        v = abs(pr - qs)
        # print("@",pr,qs,v)
        if v < mint:
            mint = v
            p = pr
            q = qs
        else:
            break
    return p,q


minu = s
for i in range(2,len(A)-1):
    p,q = df(0,i)
    r,s = df(i,len(A))
    # print((p,q,r,s))
    t = max(p,q,r,s) - min(p,q,r,s)
    if t < minu:
        minu = t
print(minu)


# Example run
# Input:
2817
-15415740
# Output:
-15415740
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N):
	for j in range(i + 1, N):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			temp = max(P, Q, R, S) - min(P, Q, R, S)
			if temp < ans:
				ans = temp
print(ans)


# Example run
# Input:
-37376338
32168745
# Output:
10000000000
def hersCode(L, x):
  ng = 0
  ok = len(L) - 1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if L[mid] > x:
      ok = mid
    else:
      ng = mid
  return ok

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

cs = [0] * N
cs[0] = A[0]
for i in range(1, N):
  cs[i] = cs[i-1] + A[i]

t = hersCode(cs,(cs[N - 2] - A[0]) // 2)
b = 0
c = t
d = N - 2
e = N - 1
B = cs[b]
C = cs[c] - cs[b]
D = cs[d] - cs[c]
E = cs[e] - cs[d]

Ans = max(B, C, D, E) - min(B, C, D, E)
while True:
  if B >= C and B >= D and E >= C and E >=D:
    break
  if B + A[b + 1] < E + A[d]:
    B += A[b + 1]
    C -= A[b + 1]
    b += 1
  else:
    E += A[d]
    D -= A[d]
    d -= 1
  while True:
    t = C - D
    if t >= 0:
      if abs(t - 2 * A[c]) < t:
        C -= A[c]
        D += A[c]
        c -= 1
      else:
        break
    else:
      if abs(-t - 2 * A[c + 1]) < -t:
        C += A[c + 1]
        D -= A[c + 1]
        c += 1
      else:
        break
  t = max(B, C, D, E) - min(B, C, D, E)
  if Ans > t:
    Ans = t
print(Ans)

# Example run
# Input:
1
4887419
# Output:
4887419
N=int(input())
 
A=list(map(int,input().split()))
 
fourdivide=sum(A)//4
P=Q=R=S=0
Pflag=Qflag=Rflag=0
Pindex=Qindex=Rindex=0
Ppre=Qpre=Rpre=Spre=0
answer=10**9

def intr(a,b,c):
	global answer
	d=sum(A)-a-b-c
	answer=min(answer,max(a,b,c,d)-min(a,b,c,d))

for i in range(N):
	if Pflag==0 and i<=N-4:
		P+=A[i]
		if P>=fourdivide:
			Pflag=1
			Pindex=i
			if i!=0:
				Ppre=P-A[i]
	elif Qflag==0 and i<=N-3:
		Q+=A[i]
		if Q>=fourdivide:
			Qflag=1
			Qindex=i
			Qpre=Q-A[i]
	elif Rflag==0 and i<=N-2:
		R+=A[i]
		if R>=fourdivide:
			Rflag=1
			Rindex=i
			Rpre=R-A[i]            

intr(P,Q,R)
if Rpre!=0:
	intr(P,Q,Rpre)
Rflag=0
QpreR=QpreRpre=0

for i in range(Qindex,N):
	if Rflag==0 and i<=N-2:
		QpreR+=A[i]
		if QpreR>=fourdivide:
			Rflag=1
			Rindex=i
			QpreRpre=QpreR-A[i]

if Qpre!=0 and QpreR!=0:
	intr(P,Qpre,QpreR)
if Qpre!=0 and QpreRpre!=0:
	intr(P,Qpre,QpreRpre)

Qflag=0
Rflag=0
PpreQ=PpreQpre=0
PpreR=PpreRpre=0

if Ppre!=0:
	for i in range(Pindex,N):
		if Qflag==0 and i<=N-3:
			PpreQ+=A[i]
			if PpreQ>=fourdivide:
				Qflag=1
				Qindex=i
				PpreQpre=PpreQ-A[i]
		elif Rflag==0 and i<=N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	if Ppre!=0 and PpreQ!=0 and PpreR!=0:
		intr(Ppre,PpreQ,PpreR)
	if Ppre!=0 and PpreQ!=0 and PpreRpre!=0:
		intr(Ppre,PpreQ,PpreRpre)
	Rflag=0
	PpreQpreR=PpreQpreRpre=0
	for i in range(Qindex,N):
		if Rflag==0 and i<=N-2:
			PpreQpreR+=A[i]
			if PpreQpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreQpreRpre=PpreQpreR-A[i]
	if Ppre!=0 and PpreQpre!=0 and PpreQpreR!=0:
		intr(Ppre,PpreQpre,PpreQpreR)
	if Ppre!=0 and PpreQpre!=0 and PpreQpreRpre!=0:
		intr(Ppre,PpreQpre,PpreQpreRpre)
      



print(answer)

# Example run
# Input:
-1
-3439167
# Output:
3439167
n=int(input())
*a,=map(int,input().split())

def func2(a,i):   
    bb,bc=func3(a[:i])
    cb,cc=func3(a[i:])
    *l,=map(sum,[bb,bc,cb,cc])
    return abs(max(l)-min(l))

def func3(b):
    i=0
    s=10**10
    m,n=0,sum(b)
    for j in range(len(b)-1):
        m+=b[j]
        n-=b[j]
        t=abs(m-n)
        if s>t:
            s=t
            i=j+1
        else:
            break
    return b[:i],b[i:]

m=10**10
for i in range(2,n-1):
    t=func2(a,i)
    if t<m:
        m=t
print(m)

# Example run
# Input:
-1005
39756387
# Output:
10000000000
# 2つの部分列に分ける
def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  # start = 0のときcumA[-1] = 0

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    # okかok+1
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

N = int(input())
A = [int(x) for x in input().split()]

cumA = [A[0]] + [0] * N  # 累積和  cumA[-1] = 0となるように最後にダミー
for i in range(1, N):
    cumA[i] = cumA[i - 1] + A[i]

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]
# 3本の境界線のうち中央を探す
for i in range(1, N - 2):
    B[0] = eqcut(0, i)  # A[0], ..., A[i]を要素の総和が最小となる2つの部分列に分ける
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

    ans = min(ans, max(S) - min(S))

print(ans)

# Example run
# Input:
0
-6956
# Output:
-6956
n=int(input())
a=[int(i) for i in input().split()]

s=[a[0]]
for i in range(n-1):
	s.append(s[i]+a[i+1])
ans=s[n-1]
j=0
k=2
for i in range(1,n-2):
	while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
		j=j+1
	while abs(s[n-1]-2*s[k]+s[i]) > abs(s[n-1]-2*s[k+1]+s[i]):
		k=k+1
	t=max(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])-min(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])
	if ans>t:
		ans=t
print(ans)


# Example run
# Input:
1
-816653
# Output:
-816653
from bisect import bisect_right, bisect_left
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
A = [0] + A
a = list(accumulate(A))
answer = a[-1]

# 切り口はN-1個, 真ん中の選び方はN-3
for i in range(N - 3):
    left = a[i + 2]
    right = a[-1] - left
    p = bisect_left(a, left // 2)
    P1 = a[p]
    Q1 = left - P1
    P2 = a[p - 1]
    Q2 = left - P2
    if abs(P1 - Q1) <= abs(P2 - Q2):
        P = P1
        Q = Q1
    else:
        P = P2
        Q = Q2

    s = bisect_right(a, a[-1] - right // 2)
    S1 = a[-1] - a[s - 1]
    R1 = right - S1
    S2 = a[-1] - a[s]
    R2 = right - S2
    if abs(S1 - R1) <= abs(S2 - R2):
        S = S1
        R = R1
    else:
        S = S2
        R = R2

    answer = min(answer, max(P, Q, R, S) - min(P, Q, R, S))

print(answer)

# Example run
# Input:
-49958
-1043639
# Output:
-1043639
n = int(input())
A = tuple(map(int, input().split()))
L = len(A)
B = [0]*L
s = 0
for i,v in enumerate(A):
    s += v
    B[i] = s

def sumf(i,j):
    global B
    if i == 0:
        return B[j]
    else:
        return B[j] - B[i-1]

def dv(a,b):
    r = b - a + 1
    x,y = 0,0
    while r > 0:
        if x < y:
            x += A[a]
            a += 1
        else:
            y += A[b]
            b -= 1
        r -= 1
    return x,y

minu = s
for i in range(2,L-1):
    p,q = dv(0,i-1)
    r,s = dv(i,L-1)
    t = max(p,q,r,s) - min(p,q,r,s)
    if minu > t:
        minu = t

print(minu)


# Example run
# Input:
0
-1098720
# Output:
-1098720
a = int(input())
b = [int(i) for i in input().split()]
n = float("inf")
for i in range(a):
     for j in range(i+1,a):
         for k in range(j+1,a):
             m = [sum(b[:i]),sum(b[i:j]),sum(b[j:k]),sum(b[k:])]
             t = max(m) - min(m)
             if t < n:
                 n = t
print(n)

# Example run
# Input:
-181
1419428
# Output:
inf
N = int(input())
A = list(map(int, input().split()))

ans=sum(A)
for a in range(3,N):
  for b in range(2,a):
    for c in range(1,b):
      sum1=sum(A[:c])
      sum2=sum(A[c:b])
      sum3=sum(A[b:a])
      sum4=sum(A[a:])
      dif=max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4)
      if dif<ans:
        ans=dif
      if sum2<=sum1:
        break
    if min(sum1,sum2,sum3)==sum3:
      break
  if min(sum1,sum2,sum3,sum4)==sum4:
    break

print(ans)

# Example run
# Input:
59663
89593766
# Output:
89593766
N = int(input())
A = list(map(int, input().split()))
cum_sum = [0] + [sum(A[:i + 1]) for i in range(N)]

ans = float("inf")


def get_diff(left, center, right):
    return abs((cum_sum[center] - cum_sum[left]) - (cum_sum[right] - cum_sum[center]))


l_point = 1
r_point = 3

for C in range(2, N):
    while l_point + 1 < C and get_diff(0, l_point, C) > get_diff(0, l_point + 1, C):
        l_point += 1
    while r_point + 1 < N and get_diff(C, r_point, N) > get_diff(C, r_point + 1, N):
        r_point += 1

    pqrs = [cum_sum[l_point], cum_sum[C] - cum_sum[l_point], cum_sum[r_point] - cum_sum[C], cum_sum[N] - cum_sum[r_point]]
    ans = min(ans, max(pqrs) - min(pqrs))

print(ans)


# Example run
# Input:
228552
-24756136
# Output:
24756136
N = int(input())
A = [0] + list(map(int, input().split()))
for i in range(1, N + 1):
    A[i] += A[i - 1]


# print (A)

ans = 10 ** 9

#基準を求める
stan = A[N]//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)

stan = (A[N] + 3)//4

for i in range(2 ** 3):
    PQRS = [0, 0, 0, 0]
    index = 1
    prev_index = 0
    for j in range(3):
        if (i >> j) & 1: #基準以上にするとき
            while A[index] - A[prev_index] < stan and index < N:
                index += 1
            PQRS[j] = A[index] - A[prev_index]
            prev_index = index
            # print (1, end = '')
        else: #基準以下にするとき
            while A[index] - A[prev_index] < stan and index < N + 1:
                index += 1
                if index == N + 1:
                    break
            PQRS[j] = A[index - 1] - A[prev_index]
            prev_index = index - 1
            # print (0, end = '')
    PQRS[3] = A[N] - A[prev_index]
    # print (PQRS, end = ' ')
    # print (max(PQRS) - min(PQRS))
    ans = min((max(PQRS) - min(PQRS)), ans)


print (ans)

# Example run
# Input:
0
-6956
# Output:
0
from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(acc(map(int,input().split())))

ans=a[-1]
p=0
q=2
for j in range(1,N-2):
    q=max(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        q+=1

    x=[ a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q] ]
    ans=min(ans, max(x)-min(x))

print(ans)

# Example run
# Input:
-2147483648
450137
# Output:
450137