Felix6326727/beyond-accuracy-code-comprehension huggingface dataset:
# -*- coding: utf-8 -*-
from itertools import combinations

n = int(input())
a = [int(_) for _ in input().split()]

combs = combinations(range(1, n), 3)

grief = 10**10
for comb in combs:
    p = sum(a[:comb[0]])
    q = sum(a[comb[0]:comb[1]])
    r = sum(a[comb[1]:comb[2]])
    s = sum(a[comb[2]:])

    tmp = max(p, q, r, s) - min(p, q, r, s)
    if tmp < grief:
        grief = tmp

print(grief)


# Example run
# Input:
-9486
-1394868732
# Output:
10000000000
N = int(input())
A = list(map(int, input().split()))

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
nextJ, nextK = -1, -1
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    nextJ = max(nextJ, 0)
    for j in range(nextJ, i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = abs(sumB - sumC)
        if buf > d:
            buf = d
            P = sumB
            Q = sumC
            nextJ = j
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    nextK = max(nextK, (i + 1))
    for k in range(nextK, (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = abs(sumD - sumE)
        if buf > d:
            buf = d
            R = sumD
            S = sumE
            nextK = k
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

# Example run
# Input:
-154
1
# Output:
inf
def get_num_f(data, sum_data):
    left1, left2 = 0, sum_data
    for i in range(len(data)- 1):
        if left1 + data[i] >= left2 - data[i]:
            pre_d = abs(left1 - left2)
            now_d = abs((left1 + data[i]) - (left2 - data[i]))
            if now_d < pre_d:
                left1 += data[i]
                left2 -= data[i]
            break
        left1 += data[i]
        left2 -= data[i]
    return left1, left2




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

    sum_left, sum_righ = sum(data[:2]), sum(data[2:])
    left1, left2 = get_num_f(data[:2], sum_left)
    righ1, righ2 = get_num_f(data[2:], sum_righ)

    ans = max(left1, left2, righ1, righ2) - min(left1, left2, righ1, righ2)

    for i in range(2, num - 2):
        sum_left += data[i]
        sum_righ -= data[i]
        left1, left2 = get_num_f(data[:i + 1], sum_left)
        righ1, righ2 = get_num_f(data[i + 1:], sum_righ)
        ans_kari = max(left1, left2, righ1, righ2) - min(left1, left2, righ1, righ2)

        if ans_kari < ans:
            ans = ans_kari

    print(ans)



if __name__ == '__main__':
    main()

# Example run
# Input:
-119860
-398
# Output:
398
from statistics import mean

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

S = [A[0]]
for i in range(1, N):
    S.append(S[i - 1] + A[i])   

A = 0
C = 0
SUM_ALL = S[-1]
answer = SUM_ALL

for B in range(2, N - 1):
    C = max(B + 1, C)
    SA = S[A]
    SB = S[B] - S[A]
    SC = S[C] - S[B]
    SD = SUM_ALL - S[C]

    left_score = abs(SA - SB)
    while True:
        A_ = A + 1
        SA_ = S[A_]
        SB_ = S[B] - SA_
        diff = abs(SA_ - SB_)
        if left_score > diff:
            A, SA, SB, left_score = A_, SA_, SB_, diff
        else:
            break
    
    right_score = abs(SD - SC)
    while True:
        C_ = C + 1
        SC_ = S[C_]
        SD_ = SUM_ALL - SD_
        diff = abs(SC_ - SD_)
        if right_score > diff:
            C, SC, SD, right_score = C_, SC_, SD_, diff
        else:
            break
    
    score = max(SA, SB, SC, SD) - min(SA, SB, SC, SD)
    answer = min(score, answer)

print(answer)




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

def func2(a):
    m=10**9+1
    mi=0
    for i in range(len(a)):
        try:
            t=abs(sum(a[:i])-sum(a[i:]))
            if t<m:
                m=t
                mi=i   
        except:
            pass
    return a[:mi],a[mi:]
  
b,c=func2(a)
l=[]
if len(b)!=1:
    bb,bc=func2(b)
    if len(c)!=1:
        cb,cc=func2(c)
        l.append([bb,bc,cb,cc])
    else:
        if len(bb)!=1:
            bbb,bbc=func2(bb)
            l.append([bbb,bbc,bc,c])
        else:
            bcb,bcc=func2(bc)
            l.append([bb,bcb,bcc,c])
if len(c)!=1:
    cb,cc=func2(c)
    if len(b)!=1:
        bb,bc=func2(b)
        l.append([bb,bc,cb,cc])
    else:
        if len(cb)!=1:
            cbb,cbc=func2(cb)
            l.append([b,cbb,cbc,cc])
        else:
            ccb,ccc=func2(cc)
            l.append([b,cb,ccb,ccc])
            
v=10**9+1
for li in l:
    *t,=map(sum,li)
    tt=abs(max(t)-min(t))
    if v>tt:
        v=tt
print(v)

# Example run
# Input:
-1709982756
-5830
# Output:
5830
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)
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]
 
intr(P,Qpre,QpreR)
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 N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	intr(Ppre,PpreQ,PpreR)
	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]
	intr(Ppre,PpreQpre,PpreQpreR)
	intr(Ppre,PpreQpre,PpreQpreRpre)
      
 
 
 
print(answer)

# Example run
# Input:
-61684020
84816755
# Output:
84816755
from itertools import accumulate
import bisect

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

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=L-1
  R2=R-1
  res=10**10
  if R < N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2],cnt-S[L2],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2 < N:
    ans3=[S[L],cnt-S[L],S[R2]-cnt,S[N-1]-S[R2]]
    ans4=[S[L2],cnt-S[L2],S[R2]-cnt,S[N-1]-S[R2]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)

# Example run
# Input:
-16860
0
# Output:
10000000000
from itertools import accumulate

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

sum_a = list(accumulate(A))
lft = 0
rgt = 2
t = sum_a[-1]
ans = t

for i in range(1,N-2):
    # P<=Q となるように左側の仕切りを動かす
    while sum_a[i] > sum_a[lft] + sum_a[lft+1]:
        lft += 1
        
    while t + sum_a[i] > sum_a[rgt] + sum_a[rgt+1]:
        rgt += 1
        
    p = sum_a[lft]
    q = sum_a[i] - p
    r = sum_a[rgt] - q - p
    s = t - r - q - p
    
    ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    
print(ans)

# Example run
# Input:
-211506
229086910
# Output:
229086910
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
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				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:
-3
0
# Output:
0
n=int(input())
xs=[int(s) for s in input().split()]
for i in range(1,n):
    xs[i]+=xs[i-1]
xs_last=xs[n-1]
ans=xs_last
l=0
r=2
for c in range(1,n-2):
    xs_center=xs[c]
    while l<c-1:
        if xs_center<xs[l+1]*2:
            if (xs[l+1]+xs[l])<xs_center:
                l+=1
            break
        l+=1
    while r<n-2:
        if xs_last+xs_center<2*xs[r+1]:
            if (xs[r+1]+xs[r])<xs_last+xs_center:
                r+=1
            break
        r+=1
    pqrs=[xs[l],xs_center-xs[l],xs[r]-xs_center,xs_last-xs[r]]
    ans=min(ans,max(pqrs)-min(pqrs))
print(ans)
            
    

# Example run
# Input:
1
0
# Output:
0
n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[i] + a[i])
ans = s[n] + 1

for x in range(n):
    for y in range(x + 1, n):
        for z in range(y + 1, n):
            b = s[x] - s[0]
            c = s[y] - s[x]
            d = s[z] - s[y]
            e = s[n] - s[z]
            diff = max(b, c, d, e) - min(b, c, d, e)
            ans = min(diff, ans)

print(ans)

# Example run
# Input:
0
297514
# Output:
1
N = int(input())
A = list(map(int,input().split()))

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a = 1
c = 3
ans = S[N]

for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        ans = min(ans,(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])))

print(ans)

# Example run
# Input:
1
-1
# Output:
-1
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=s[-1]
p=0
q=2
for i in range(2,N-1):
    while abs(s[i-1]-2*s[p])>abs(s[i-1]-2*s[p+1]):
        p+=1
    while abs(s[q]*2-s[i-1]-s[-1])>abs(s[q+1]*2-s[i-1]-s[-1]):
        q+=1
    t=[s[i-1]-s[p],s[p],s[q]-s[i-1],s[-1]-s[q]]
    ans=min(ans,max(t)-min(t))
print(ans)    

# Example run
# Input:
-199220713
-51132021
# Output:
-51132021
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans = A_sum[N-1]
for m in range(2,N-1):
    sum_left = A_sum[m-1]
    i=bisect_left(A_sum,sum_left/2)
    sum1=A_sum[i]
    if i!= 0:
        if A_sum[i]+A_sum[i-1] > sum_left:
            sum1=A_sum[i-1]
    sum2 = sum_left - sum1
    
    sum_right=A_sum[N-1]-sum_left
    i=bisect_left(A_sum,sum_left+sum_right/2)
    sum3=A_sum[i]-sum_left
    if i!=m:
        if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
            sum3=A_sum[i-1]-sum_left
    sum4=sum_right-sum3
    max_sum=max(sum1,sum2,sum3,sum4)
    min_sum=min(sum1,sum2,sum3,sum4)
    dif=max_sum-min_sum
    if dif<ans:
        ans=dif
        
print(ans)

# Example run
# Input:
0
-7617381
# Output:
-7617381
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))
	print(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)
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]

intr(P,Qpre,QpreR)
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 N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	intr(Ppre,PpreQ,PpreR)
	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]
	intr(Ppre,PpreQpre,PpreQpreR)
	intr(Ppre,PpreQpre,PpreQpreRpre)
      



print(answer)

# Example run
# Input:
-18099607
-1965718821
# Output:
0 0 0 -1965718821
0 0 0 -1965718821
0 0 0 -1965718821
0 0 0 -1965718821
1000000000
n=int(input())
a=list(map(int,input().split()))
x=sum(a)//4
p,sp=0,0
for i in range(n):
    sp+=a[i]
    p=i
    if sp>=x:
        break

def qq(p_):
    global n,a
    x=(sum(a)-sum(a[:p_+1]))//3
    q_,sq_=0,0
    for i in range(p_+1,n):
        sq_+=a[i]
        q_=i
        if sq_>=x:
            break
    return [q_-1,q_]
def rr(q_):
    global n,a
    x=(sum(a)-sum(a[:q_+1]))//2
    r_,sr_=0,0
    for i in range(q_+1,n):
        sr_+=a[i]
        r_=i
        if sr_>=x:
            break
    return [r_-1,r_]
f=[p-1,p] if p!=0 else [p]
ans=[]
for z1 in f:
    for z2 in qq(z1):
        for z3 in rr(z2):
            cand=[sum(a[:z1+1]),sum(a[z1+1:z2+1]),sum(a[z2+1:z3+1]),sum(a[z3+1:])]
            ans.append(max(cand)-min(cand))
print(min(ans))




# Example run
# Input:
-4749
11669
# Output:
11669
n = int(input())

l = list(map(int,input().split()))

acc = []

s = 0
for c in l:
    s += c
    acc.append(s)

#find the left part best bars

left = [-1]*(n-1)
# left[i] is the best bar when middle bar is between i and i+1

L = 0
M = 1

for M in range(1,n-2):
    if M == 1:
        left[M] = 0
    else:
        #judge left bar go forward or not?!
        pre_bar = left[M-1]
        pre_gap = abs(acc[pre_bar] - (acc[M]-acc[pre_bar]))
        next_bar = M-1
        for nxt_bar in range(pre_bar+1,M):
            nxt_gap = abs(acc[nxt_bar]-(acc[M]-acc[nxt_bar]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar - 1
                break
            else:
                pre_gap = nxt_gap
        left[M] = next_bar
#print(left)



#find the right part best bars
right = [-1]*(n-1)
# right[i] is the best bar when middle bar is between i and i+1

for M in range(1,n-2)[::-1]:
    if M == n-3:
        right[M] = n - 2
    else:
        #judge right bar go backward or not?!
        pre_bar = right[M+1]
        pre_gap = abs(acc[n-1]-acc[pre_bar] - (acc[pre_bar] - acc[M]))
        next_bar = M+1
        for nxt_bar in range(M+1,pre_bar)[::-1]:
            nxt_gap = abs(acc[n-1]-acc[nxt_bar] - (acc[nxt_bar]-acc[M]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar + 1
                break
            else:
                pre_gap = nxt_gap
        right[M] = next_bar
#print(right)

res = acc[n-1] + 1
for M in range(1,n-2):
    L = left[M]
    R = right[M]
    a,b,c,d = acc[L],acc[M]-acc[L],acc[R]-acc[M],acc[n-1]-acc[R]
    gap = max(a,b,c,d)-min(a,b,c,d)
    res = min(res,gap)

print(res)


# Example run
# Input:
0
5568815
# Output:
5568816
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 2):
	for j in range(i + 1, N - 1):
		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:])
			print("{} {} {} {}".format(B, C , D, E))
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)


# Example run
# Input:
-39547
-46095437
# Output:
10000000000
from itertools import *
input()
s=list(accumulate(map(int,input().split())))
l,r,t=0,2,s[-1];a=t
for m in s[1:-2]:
    while abs(t-2*s[r]+m)>abs(t-2*s[r+1]+m):r+=1
    while abs(m-2*s[l])>abs(m-2*s[l+1]):l+=1
    x=sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    a=min(a,x[3]-x[0])
print(a)

# Example run
# Input:
'gz56)B`
-2058894
# Output:
-2058894
N = int(input())
A = list(map(int,input().split()))
B,C,D,E = [],[],[],[]
b,c,d,e =0,0,0,0
ans = 10**10
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)
            if ans > abs(max(b,c,d,e)-min(b,c,d,e)):
                ans = abs(max(b,c,d,e)-min(b,c,d,e))
print(ans)

# Example run
# Input:
-2713
-322623
# Output:
10000000000
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:
-147113079
84
# Output:
83916
# https://atcoder.jp/contests/abc102/tasks/arc100_b

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

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

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

    while c <= n - 2:
        while True:
            if l == c - 1:
                break
            if abs(P - Q) < abs((P + al[l]) - (Q - al[l])):  # これ以上差が縮まらないなら break
                break

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

        while True:
            if r == n - 1:
                break
            if abs(R - S) < abs((R + al[r]) - (S - al[r])): # これ以上差が縮まらないなら break
                break

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

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

        # center を一つ右に進める
        Q += al[c]
        R -= al[c]
        c += 1

    print(ans)

if __name__ == '__main__':
    main()


# Example run
# Input:
-1477
1323998648
# Output:
1323998648
from bisect import bisect_left
N=int(input())
A=[int(i) for i in input().split()]
S=[]
for i in range(N):
  if i==0:
    S.append(A[i])
  else:
    S.append(S[i-1]+A[i])
print(S)
ans=float("inf")
for i in range(2,N):
  x=bisect_left(S[:i],S[i-1]/2)
  if abs(S[i-1]-2*S[x])<=abs(S[i-1]-2*S[x-1]):
    P=S[x]
    Q=S[i-1]-S[x]
  else:
    P=S[x-1]
    Q=S[i-1]-S[x-1]
  y=bisect_left(S[i:],(S[N-1]+S[i])/2)+i-1
  if abs(2*S[y]-S[i-1]-S[N-1])<=abs(2*S[y-1]-S[i-1]-S[N-1]):
    R=S[y]-S[i-1]
    T=S[N-1]-S[y]
  else:
    R=S[y-1]-S[i-1]
    T=S[N-1]-S[y-1]
  A=max(P,Q,R,T)
  B=min(P,Q,R,T)
  ans=min(ans,A-B)
print(ans)  
  
  

  


# Example run
# Input:
-23909
-68
# Output:
[]
inf
N = int(input())
A = [int(i) for i in input().split()]

cache = {}

def my_sum(array, begin, end):
    index = (begin, end)
    
    if index in cache:
        summary = cache[index]
    else:
        summary = sum(array[begin:end])
        cache[index] = summary
    
    return summary

diff_list = []

for c2 in range(2, N-1):
    for c1 in range(1, c2):
        P = my_sum(A, 0, c1)
        Q = my_sum(A, c1, c2)
        
        for c3 in range(c2+1, N):
            R = my_sum(A, c2, c3)
            S = my_sum(A, c3, N)
            
            max_sum = max(P, Q, R, S)
            min_sum = min(P, Q, R, S)
            
            diff_list.append(max_sum - min_sum)
            
print(min(diff_list))

# Example run
# Input:
6
654709
# Output:
654709
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

tmp = -sum(A)
LmR = [tmp]
for Ai in A[:-1]:
    tmp += 2 * Ai
    LmR.append(tmp)

# print("###", LmR)
# # b2
# tar = 0
# for b2, val in enumerate(LmR):
#     if val < tar: break
# if LmR[b2 - 1] < -LmR[b2]: b2 -= 1

ans = sum(A)
for b2 in range(2, N - 1):
    # b1
    tar = -sum(A[b2:])
    # for b1, val in enumerate(LmR):
    #     if val < tar: break
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # b3
    tar = sum(A[:b2])
    # for b3, val in enumerate(LmR):
    #     if val < tar: break
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

    parts = (sum(A[:b1]), sum(A[b1:b2]), sum(A[b2:b3]), sum(A[b3:]))
    # print("#", A[:b1], A[b1:b2], A[b2:b3], A[b3:], max(parts) - min(parts))
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

# Example run
# Input:
-2848852
-1654029
# Output:
-1654029
N=int(input())
a=list(map(int,input().split()))
def check(x):
  d = [0] * 4
  p = 0
  for i in range(N):
    d[p] += a[i]
    if d[p] >= x: p += 1
    if p > 3: p -= 1
  return min(d) >= x
def solve(l, r):
  d=[0]*4
  p=0
  for i in range(N):
    d[p] += a[i]
    if d[p] > r:
      d[p] -= a[i]
      p+=1
      if p > 3: return False
      d[p]+=a[i]
  return min(d[: p+1])>=l
ok = 0
ng = N * max(a)
m = 0
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
mn = ok+0
ng = max(mn, max(a)) - 1
ok = N * max(a)
m = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(mn, m):
    ok = m
  else: ng = m
print(ok-mn)

# Example run
# Input:
89
-4941179
# Output:
-439764931
N = int(input())
A = list(map(int,input().split()))
DIFFfix = SUM = sum(A)
for i in range(N-3):
  Q = sum(A[:i+2]); S = SUM - Q
  P = R = Pfix = Rfix = 0
  Qfix = Q; Sfix = S
  m = 0
  flag = True
  while flag:
    m += 1
    P += A[m-1]
    Q -= A[m-1]
    if abs(P-Q) < abs(Pfix - Qfix):
      Pfix = P; Qfix = Q
    else:
      flag = False
  m = 0
  flag = True
  while flag:
    m += 1
    R += A[i+m+1]
    S -= A[i+m+1]
    if abs(R-S) < abs(Rfix - Sfix):
      Rfix = R; Sfix = S
    else:
      flag = False
  DIFF = abs(max(Pfix,Qfix,Rfix,Sfix)-min(Pfix,Qfix,Rfix,Sfix))
  if DIFF < DIFFfix:
    DIFFfix = DIFF
print(DIFFfix)

# Example run
# Input:
-213
-5
# Output:
-5
N = int(input())
A = list(map(int, input().split()))
mn = float('inf')
for a in range(1,N-2):
    for b in range(a+1,N-1):
        for c in range(b+1,N):
            #print(A[:a],A[a:b],A[b:c],A[c:])
            P = sum(A[:a])
            Q = sum(A[a:b])
            R = sum(A[b:c])
            S = sum(A[c:])
            s_max = max(P,Q,R,S)
            s_min = min(P,Q,R,S)
            dif = abs(s_max - s_min)
            mn = min(mn, dif)
print(mn)


# Example run
# Input:
-84521052
-2
# Output:
inf
from itertools import accumulate
input()
*s, = accumulate(map(int, input().split()))
l,r,t = 0,2,s[-1]
c = t
for m in s[1:-2]:
    while t+m > s[r]+s[r+1]:
        r += 1
    while m > s[l]+s[l+1]:
        l += 1
    x = sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    c = min(c,x[-1]-x[0])
print(c)

# Example run
# Input:
*Q<jukmQ3
713362851
# Output:
713362851