CodeEff/ECCO huggingface dataset:
# Original solution
from statistics import mean

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

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


ans = float('inf')

for middle in range(1, N - 2):
    left_middle = 0
    right_middle = middle + 1
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

print(ans)
        


# Optimized solution
from statistics import mean

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

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

left_middle = 0
right_middle = 2

ans = float('inf')

for middle in range(1, N - 2):
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

print(ans)
# Original solution
from itertools import accumulate
import bisect


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

arev = list(reversed(a))

front = list(accumulate(a))
back = list(accumulate(arev))

ans = float('inf')
for i in range(1,n-2):
    b = bisect.bisect_left(front,front[i]//2,0,i-1)
    c = bisect.bisect_left(back,back[n-i-2]//2,0,n-i-3)

    p = front[b]
    q = front[i]-front[b]
    s = back[c]
    r = back[n-i-2]-back[c]
    ans = min(max(p,q,r,s)-min(p,q,r,s),ans)

    if b!=0:
        p = front[b-1]
        q = front[i] - front[b-1]
        s = back[c]
        r = back[n-i-2] - back[c]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)
    if c!=0:
        p = front[b]
        q = front[i] - front[b]
        s = back[c-1]
        r = back[n-i-2] - back[c-1]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)
    if b!=0 and c!=0:
        p = front[b-1]
        q = front[i] - front[b-1]
        s = back[c-1]
        r = back[n-i-2] - back[c-1]
        ans = min(max(p, q, r, s) - min(p, q, r, s), ans)

print(ans)











# Optimized solution
# 解説の方法

from itertools import accumulate

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

acc = list(accumulate(a))

l = 0
r = 2

ans = float('inf')

for y in range(1,n-2):
    for x in range(l,y-1):
        if abs(acc[y]-acc[x]*2)>=abs(acc[y]-acc[x+1]*2):
            l = x+1
            continue
        else:
            break
    r = max(y+1,r)
    for z in range(r,n-2):
        if abs(acc[n-1]-acc[z]*2+acc[y])>=abs(acc[n-1]-acc[z+1]*2+acc[y]):
            r = z+1
            continue
        else:
            break
    P = acc[l]
    Q = acc[y] - acc[l]
    R = acc[r] - acc[y]
    S = acc[n-1] - acc[r]
    ans = min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)
# Original solution
n=int(eval(input()))
a=[int(i) for i in input().split()]

s=sum(a)
ans=s
b=a[0]
for i in range(n-3):
	b=0
	for l in range(i+2):
		b+=a[l]
	c=s-b
	j=0
	k=0
	while k-b/2<0:
		k+=a[j]
		j+=1
	if k-b/2>b/2+a[j-1]-k:
		k-=a[j-1]
	x=min(k,b-k)
	y=max(k,b-k)
	j=-1
	k=0
	while k-c/2<0:
		k+=a[j]
		j-=1
	if k-c/2>c/2+a[j+1]-k:
		k-=a[j+1]
	z=min(k,c-k)
	w=max(k,c-k)
	t=max(y,w)-min(x,z)
	if ans>t:
		ans=t
print(ans)

# Optimized solution
n=int(eval(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)
# Original solution
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(eval(input()))
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
p=0
q=2
for j in range(1,N-2):
    q=min(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

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

# Optimized solution
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(eval(input()))
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
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

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)
# Original solution
from itertools import accumulate
from bisect import bisect

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( eval(input()))
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)


# Optimized solution
from itertools import accumulate

N = int( eval(input()))
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)
# Original solution
from itertools import accumulate
from bisect import bisect_left, bisect_right

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

ts = list(accumulate(a))+[0]
r = 0

def calc(st, ed):
    t0 = ts[ed-1] - ts[st-1]
    i1 = bisect_left(ts, (ts[ed-1]+ts[st-1])/2, st+1, ed-1)
    t11 = ts[i1-1] - ts[st-1]
    t12 = t0 - t11
    t21 = ts[i1] - ts[st-1]
    t22 = t0 - t21
    if abs(t22-t21) > abs(t12-t11):
        return t11, t12
    else:
        return t21, t22

ans = 10**18
for i in range(2, n-1):
    r1, r2 = calc(0, i)
    r3, r4 = calc(i, n)
    # print(r1, r2, r3, r4)
    diff = max([r1, r2, r3, r4]) - min([r1, r2, r3, r4])
    ans = min(ans, diff)

print(ans)
    



# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

from itertools import accumulate
accum = list(accumulate(a))

i_left = 0
i_right = 2
ans = 10**18
for i in range(1, n-2):
    while True:
        p = accum[i_left]
        q = accum[i] - p
        p_new = accum[i_left+1]
        q_new = accum[i] - p_new
        if abs(p_new - q_new) < abs(p - q):
            i_left += 1
        else:
            break
    while True:
        r = accum[i_right] - accum[i]
        s = accum[-1] - accum[i_right]
        r_new = accum[i_right+1] - accum[i]
        s_new = accum[-1] - accum[i_right+1]
        if abs(r_new - s_new) < abs(r - s):
            i_right += 1
        else:
            break

    # print(p, q, r, s)
    diff = max([p, q, r, s]) - min([p, q, r, s])
    ans = min(ans, diff)

print(ans)
# Original solution
import sys
from itertools import accumulate
from bisect import bisect_left as bi_l

n, *a = list(map(int, sys.stdin.read().split()))

def main():
    s = list(accumulate(a))

    ans = float('inf')
    for center in range(1, n-2):
        pq = s[center]
        left = bi_l(s, pq / 2)
        if left == 0:
            p = s[0]
        else:
            if pq - s[left] < s[left-1]:
                left -= 1
            p = s[left]
        q = pq - p

        rt = s[-1] - pq
        right = bi_l(s, pq + rt / 2)
        if right == center + 1:
            r = s[center+1] - pq
        else:
            if rt - (s[right] - pq) < s[right-1] - pq:
                right -= 1
            r = s[right] - pq
        t = rt - r

        res = sorted([p, q, r, t])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

# Optimized solution
import sys
from itertools import accumulate

n, *a = list(map(int, sys.stdin.read().split()))

def main():
    ans = float('inf')
    left = 0; right = 2
    p = a[0]; q = 0; r = sum(a[1:3]); s = sum(a[3:])
    for c in range(1, n-2):
        q += a[c]; r -= a[c]
        while left < c - 1:
            nex = a[left+1]
            if abs((q - nex) - (p + nex)) <= abs(q - p):
                q -= nex; p += nex
                left += 1
            else:
                break  
        
        while right < n - 2:
            nex = a[right+1]
            if abs((s - nex) - (r + nex)) <= abs(s - r):
                s -= nex; r += nex
                right += 1
            else:
                break

        res = sorted([p, q, r, s])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lst, min_num):
    total = lst[-1] - min_num
    # print (total)
    lb = -1
    ub = len(lst)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if lst[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = lst[ub] - min_num, lst[-1] - lst[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = lst[ub - 1] - min_num, lst[-1] - lst[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(A[:half], 0)
    R, S = calc(A[half:], A[half - 1])
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)


# Optimized solution
#PypyでもTLE A[:half]のような箇所が遅い？

N = int(eval(input()))
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] += A[i - 1]

def calc(lb, ub):
    max_num = A[ub]
    lb -= 1
    if lb == -1:
        min_num = 0
    else:
        min_num = A[lb]
    total = A[ub] - min_num
    # print (total)
    while (ub - lb) > 1:
        mid = (lb + ub)//2
        if A[mid] - min_num > total/2:
            ub = mid
        else:
            lb = mid
    # print ('ub', ub)
    a1, b1 = A[ub] - min_num, max_num - A[ub]
    diff1 = abs(b1 - a1)
    # print ('diff1', diff1)
    a2, b2 = A[ub - 1] - min_num, max_num - A[ub - 1]
    diff2 = abs(b2 - a2)
    # print ('diff2', diff2)
    if diff2 < diff1:
        a1, b1 = a2, b2
    return a1, b1

# print (calc(A, 0))
# half = 2
# P, Q = calc(0, half - 1)
# print (P, Q)

ans = 10 ** 9
for half in range(2, N - 1):
    # print (A[:half], end = ' ')
    # print (A[half:])
    P, Q = calc(0, half - 1)
    R, S = calc(half, N - 1)
    # print (P, Q, R, S)
    tmp = max(P, Q, R, S) - min(P, Q, R, S)
    # print (tmp)
    ans = min(tmp, ans)

# print ('ans', ans)
print (ans)
# Original solution
from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    odiff = None
    for c in range(start, end+1):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q

if __name__ == '__main__':
    # read input
    n = int(eval(input()))
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        (c1, mb, mc) = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

# Optimized solution
from itertools import accumulate

def Sdiff(s, m, e):
    # Sdiff(s, m, e) = [A_s, A_s+1 ..., A_m] [A_m+1 .... A_e]
    #    L = cl[m]-cl[s-1], R = cl[e] - cl[m]
    # diff(L,R) = abs(cl[m] - cl[s-1] - cl[e] + cl[m]) = abs(2*cl[m] - cl[s-1] - cl[e])

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        #print("partial loop: c:{}, diff:{} -> {}".format(c, odiff, diff))
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    # read input
    N = int(eval(input()))
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: N]))
        # LEFT
        c1 = partial(0, i, c1)
        # RIGHT
        c3 = partial(i+1, N-1, c3)

        # evaluate
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

    print(result)
# Original solution
N = int(eval(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)


# Optimized solution
import sys
 
n = int(eval(input()))
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])
 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)
# Original solution
#dame datta
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    Al = [A[0]]
    r = (10**9)*(2*(10**5))
    for i in A[1:]:
        Al.append(Al[-1] + i)
    for t in range(2, N-1):
        t1 = -1
        m = (10**9)*(2*(10**5))
        for i in range(1,t):
            ii = abs(Al[t-1] - Al[i-1] - Al[i-1])
            if m > ii:
                t1 = i
                m = ii
        t2 = -1
        m = (10**9)*(2*(10**5))
        for i in range(t+1, N):
            ii = abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
            if m > ii:
                t2 = i
                m = ii
        x = Al[-1] - Al[t2-1]
        y = Al[t2-1] - Al[t-1]
        z = Al[t-1] - Al[t1-1]
        w = Al[t1-1]
        r = min(max(x,y,z,w) - min(x,y,z,w), r)
    return r
print((main()))


# Optimized solution
#dame datta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        t = fn(m+1) - fn(m)
        if t == 0:
            return fn(m)
        if t < 0:
            l = m + 1
        else:
            r = m
    if fn(l) < fn(r):
        return l
    else:
        return r
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    Al = [A[0]]
    r = (10**9)*(2*(10**5))
    for i in A[1:]:
        Al.append(Al[-1] + i)
    for t in range(2, N-1):
        def fn1(i):
            return abs(Al[t-1] - Al[i-1] - Al[i-1])
        t1 = binsearch(1, t, fn1)
        def fn2(i):
            return abs(Al[-1] - Al[i-1] - Al[i-1] + Al[t-1])
        t2 = binsearch(t+1, N, fn2)
        x = Al[-1] - Al[t2-1]
        y = Al[t2-1] - Al[t-1]
        z = Al[t-1] - Al[t1-1]
        w = Al[t1-1]
        r = min(max(x,y,z,w) - min(x,y,z,w), r)
    return r
print((main()))
# Original solution
N=int(eval(input()))
a=[int(i) for i in input().split()]

from itertools import accumulate
l=[0]+list(accumulate(a))
s=l[-1]
ans=10000000000000
import bisect
for i in range(2,N-1):
    ll=l[0:i+1]
    lr=l[i:N+1]
    lls=ll[-1]
    lrs=lr[-1]-lr[0]
    n=bisect.bisect_left(ll,lls//2)
    if n+1>=len(ll):
        n=len(ll)-2
    elif n+1<0:
        n=1
    if min(abs(lls-ll[n]*2),abs(lls-ll[n-1]*2),abs(lls-ll[n+1]*2))==abs(lls-ll[n]*2):
        s=ll[n]
        t=lls-ll[n]
    elif min(abs(lls-ll[n]*2),abs(lls-ll[n-1]*2),abs(lls-ll[n+1]*2))==abs(lls-ll[n-1]*2):
        s=ll[n-1]
        t=lls-ll[n-1]
    else:
        s=ll[n+1]
        t=lls-ll[n+1]
        
    
        
    n=bisect.bisect_left(lr,lr[0]+lrs//2)
    if n+1>=len(lr):
        n=len(lr)-2
    elif n-1<0:
        n=1
    if min(abs(lrs-lr[n]*2+2*lr[0]),abs(lrs-lr[n-1]*2+2*lr[0]),abs(lrs-lr[n+1]*2+2*lr[0]))==abs(lrs-lr[n]*2+2*lr[0]):
        u=lr[n]-lr[0]
        v=lrs-lr[n]+lr[0]
    elif min(abs(lrs-lr[n]*2+2*lr[0]),abs(lrs-lr[n-1]*2+2*lr[0]),abs(lrs-lr[n+1]*2+2*lr[0]))==abs(lrs-lr[n-1]*2+2*lr[0]):
        u=lr[n-1]-lr[0]
        v=lrs-lr[n-1]+lr[0]
    else:
        u=lr[n+1]-lr[0]
        v=lrs-lr[n+1]+lr[0]
    

    ans=min(ans,max(s,t,u,v)-min(s,t,u,v))

print(ans)
    
    







# Optimized solution
n=int(eval(input()))
a=[int(i) for i in input().split()]

for i in range(n-1):
    a[i+1]+=a[i]

j=0
k=2
ans=10**9

for i in range(1,n-1):
    while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):
        j+=1
    while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):
        k+=1
    t=[a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k]]
    ans=min(ans,max(t)-min(t))
print(ans)
# Original solution
# 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(eval(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 abs(P - Q) < abs((P + al[l]) - (Q - al[l])):  # これ以上差が縮まらないなら break
                break

            if l == c - 1:
                break

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

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


# Optimized solution
# 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(eval(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()
# Original solution
from itertools import accumulate
import bisect

N=int(eval(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=bisect.bisect_right(S,cnt/2)
  R2=bisect.bisect_right(S,(cnt+S[N-1])/2)
  res=10**10
  if R!=N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2-1],cnt-S[L2-1],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-1]-cnt,S[N-1]-S[R2-1]]
    ans4=[S[L2-1],cnt-S[L2-1],S[R2-1]-cnt,S[N-1]-S[R2-1]]
    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)

# Optimized solution
from itertools import accumulate
import bisect

N=int(eval(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)