CodeEff/ECCO huggingface dataset:
# Original solution
def solve():
    N = int(eval(input()))
    A = tuple(map(int, input().split()))

    from itertools import accumulate
    CA = list(accumulate(A))

    mindiff = CA[-1]

    for c in range(1,N-2):
        # left side
        p = 0
        q = CA[-1]
        left = 0
        # for i in range(0, c):
        while True:
            pi = CA[left]
            qi = CA[c] - CA[left]
            if abs(pi- qi) >= abs(p - q):
                break
            p = pi; q = qi
            left += 1

        # right side
        r = 0
        s = CA[-1]
        right = c+1
        # for i in range(c+1, N):
        while True:
            ri = CA[right] - CA[c]
            si = CA[-1] - CA[right]
            if abs(ri- si) >= abs(r - s):
                break
            r = ri; s = si
            right += 1
    
        mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
    return mindiff
print((solve()))

# Optimized solution
N = int(eval(input()))
A = tuple(map(int, input().split()))

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while True:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right] - CA[c]
    s = CA[-1] - CA[right]
    while True:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

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

leftMiddle = 0
rightMiddle = 2

ans = float('inf')

for middle in range(2, N-1) :
    leftS = S[leftMiddle]
    rightS = S[middle] - leftS
    diff = abs(leftS - rightS)

    # 左側の更新
    for i in range(leftMiddle, middle) :
        leftS += A[i]
        rightS -= A[i]
        if diff > abs(leftS - rightS) :
            leftMiddle += 1
            diff = abs(leftS - rightS)
        else :
            break

    leftS = S[rightMiddle] - S[middle]
    rightS = S[-1] - S[rightMiddle]
    diff = abs(leftS - rightS)

    # 右側の更新
    for i in range(rightMiddle, N) :
        leftS += A[i]
        rightS -= A[i]
        if diff > abs(leftS - rightS) :
            rightMiddle += 1
            diff = abs(leftS - rightS)
        else :
            break

    B = S[leftMiddle]
    C = S[middle] - B
    D = S[rightMiddle] - S[middle]
    E = S[-1] - B - C - D

    diff = max(B, C, D, E) - min(B, C, D, E)
    ans = min(ans, diff)

print(ans)



# Optimized solution
N = int(eval(input()))
A = tuple(map(int, input().split()))

def calc(B):
    P, Q = B[0], B[1]
    ret = [None] * N
    ret[1] = (P, Q)
    mid = 1

    for right in range(2, N - 2):
        Q += B[right]
        while mid < right:
            newP = P + B[mid]
            newQ = Q - B[mid]

            if abs(newP - newQ) >= abs(P - Q):
                break
            mid += 1
            P = newP
            Q = newQ

        ret[right] = (P, Q)

    return ret

left = calc(A)[1: -2]
right = calc(A[:: -1])[1: -2][:: -1]

ans = 10**10
for (P, Q), (R, S) in zip(left, right):
    ans = min(ans, abs(max(P, Q, R, S) - min(P, Q, R, S)))

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

def found_cut(X):
    p1 = sum(X)/2
    count1 = 0
    for i in range(len(X)):
        count1 += X[i]
        if p1 <= count1:
            if abs(count1-p1) < abs(count1-X[i]-p1):
                index = i
                break
            else:
                index = i-1
                break
    return index

def found_ans(X,Y,Z,W):
    ans_list = []
    ans_list.append(sum(X))
    ans_list.append(sum(Y))
    ans_list.append(sum(Z))
    ans_list.append(sum(W))
    return max(ans_list)-min(ans_list)

ANS = []
for x in range(1,N-2):
    A_first = A[:x+1]
    A_second = A[x+1:]
    if len(A_first) >= 2 and len(A_second) >= 2:
        wp1 = found_cut(A_first)
        wp2 = found_cut(A_second)
        pattern3_1 = A_first[:wp1+1]
        pattern3_2 = A_first[wp1+1:]
        pattern3_3 = A_second[:wp2+1]
        pattern3_4 = A_second[wp2+1:]
        ANS.append(found_ans(pattern3_1,pattern3_2,pattern3_3,pattern3_4))
print((min(ANS)))

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

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 2*10**14
l = 0
temp = 2*10**14
r = 2
#for i in range(2, N):
#    if abs(S[-1]-2*S[i]+S[1]) < temp:
#        temp = abs(S[-1]-2*S[r]+S[1])
#        r = i
        
for i in range(2, N-1):
    r = max(r, i)
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r+1 < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)
# Original solution
from bisect import bisect_left

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

s = sum(A)
for i in range(1, N) :
    A[i] += A[i-1]


def check(d) :
    ifr = bisect_left(A, (s - 3 * d) // 4)
    ito = bisect_left(A, (s + 3 * d) // 4)
    for i in range(ifr, min(N, ito + 1)) :
        jfr = bisect_left(A, A[i] + (s - A[i] - 2 * d) // 3)
        jto = bisect_left(A, A[i] + (s - A[i] + 2 * d) // 3)
        for j in range(max(i + 1, jfr), min(N, jto + 1)) :
            kfr = bisect_left(A, A[j] + (s - A[j] - d) // 2)
            kto = bisect_left(A, A[j] + (s - A[j] + d) // 2)
            for k in range(max(j + 1, kfr), min(N - 1, kto + 1)) :
                cut = [A[i], A[j] - A[i], A[k] - A[j], s - A[k]]
                if max(cut) - min(cut) <= d :
                    return True
    return False

ng, ok = 0, s
while ok - ng > 1 :
    mid = (ng + ok) // 2
    
    if check(mid) :
        ok = mid
    else :
        ng = mid

print(ok)

# Optimized solution
from bisect import bisect_left

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

s = sum(A)
for i in range(1, N) :
    A[i] += A[i-1]

ret = float('inf')
for b in range(1, N - 1) :
    a = bisect_left(A, A[b] / 2)
    c = bisect_left(A, A[b] + (s - A[b]) / 2)
    for i in [a - 1, a] :
        for j in [c - 1, c] :
            if not 0 <= i < b < j < N - 1 :
                continue
            cut = [A[i], A[b] - A[i], A[j] - A[b], s - A[j]]
            ret = min(ret, max(cut) - min(cut))
            
print(ret)
# Original solution
N = int(eval(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
        else:
            break
    ##右側の区間の左端は(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
        else:
            break
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

# Optimized solution
##https://beta.atcoder.jp/contests/abc102/submissions/2779056
n = int(eval(input()))
a = list(map(int, input().split()))
s = [a[0]]
for i in range(n-1):
    s.append(s[i] + a[i+1])
ans = s[n-1]

##i,j,kは左側の区間の右端
##iは1からN-3まで
j = 0
k = 2             
for i in range(1, (n - 3) + 1):
    ##BC(i)DE
    ##BCの区間[0, i]: 最低でも2要素→0,1を取るのでi=1から
    ##DEの区間[i+1, N-1]: 最低でも2要素→N-2, N-1を取るので、i+1=N-2よりi=N-3まで

    ##B(j)C(i)DE
    #Bの区間[0, j]
    #Cの区間[j+1, i]
    ##sumB = s[j]
    ##sumC = s[i] - s[j]
    while abs(s[i] - 2 * s[j]) > abs(s[i] - 2 * s[j+1]):
        j += 1

    ##B(j)C(i)D(k)E
    #Dの区間[i+1, k]
    #Eの区間[k+1, N-1]
    ##sumD = s[k] - s[i]
    ##sumE = s[N-1] - s[k]
    while abs(s[n-1] - 2 * s[k] + s[i]) > abs(s[n-1] - 2 * s[k+1] + s[i]):
        k += 1
             
    pqrs = list((s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k]))
    ans = min(ans, max(pqrs) - min(pqrs))
print(ans)
# Original solution

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(eval(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()

# Optimized solution

def main():
    num = int(eval(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()
# Original solution
# -*- coding: utf-8 -*-
from itertools import combinations

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

combs = combinations(list(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)


# Optimized solution
# -*- coding: utf-8 -*-
n = int(eval(input()))
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# 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)  # running time limit error

# solution below ######################################

cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff = two_pointers(0, i, l_split, 10**12)
    # right
    r_split, r_diff = two_pointers(i, n, r_split, 10**12)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))


print((min(griefs)))
# Original solution
from itertools import accumulate
from bisect import bisect_left

N, *A = list(map(int, open(0).read().split()))

A = [0] + list(accumulate(A))

ans = float("inf")
for i in range(2, N - 1):
    lm = A[i] // 2
    l = bisect_left(A, lm)
    if abs(A[l - 1] - lm) < abs(A[l] - lm):
        l -= 1

    rm = (A[i] + A[N]) // 2
    r = bisect_left(A, rm)
    if abs(A[r - 1] - rm) < abs(A[r] - rm):
        r -= 1

    P = A[l]
    Q = A[i] - A[l]
    R = A[r] - A[i]
    S = A[N] - A[r]

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

print(ans)


# Optimized solution
from itertools import accumulate
from bisect import bisect_left

def main():
    N, *A = list(map(int, open(0).read().split()))

    A = [0] + list(accumulate(A))

    ans = float("inf")
    for i in range(2, N - 1):
        lm = A[i] // 2
        l = bisect_left(A, lm)
        if abs(A[l - 1] - lm) < abs(A[l] - lm):
            l -= 1

        rm = (A[i] + A[N]) // 2
        r = bisect_left(A, rm)
        if abs(A[r - 1] - rm) < abs(A[r] - rm):
            r -= 1

        P = A[l]
        Q = A[i] - A[l]
        R = A[r] - A[i]
        S = A[N] - A[r]

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

    print(ans)

main()
# Original solution
N = int(eval(input()))
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0

for r in range(2, N - 1):
    # 左のしゃくとり
    P, Q = P2, Q2 = -1, -1
    p = 0
    q = 1
    while True:
        P2, Q2 = P, Q
        P = SUM[q - 1]
        Q = SUM[r - 1] - SUM[q - 1]
        if P < Q and q < r:
            q += 1
        else:
            break
    left_min, left_max = min(P, Q), max(P, Q)
    if P2 != -1:
        if abs(Q - P) > abs(Q2 - P2):
            left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右のしゃくとり
    R, S = R2, S2 = -1, -1
    s = r + 1
    while True:
        R2, S2 = R, S
        R = SUM[s - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[s - 1]
        if R < S and s < N - 1:
            s += 1
        else:
            break
    right_min, right_max = min(R, S), max(R, S)
    if R2 != -1:
        if abs(R - S) > abs(R2 - S2):
            right_min, right_max = min(R2, S2), max(R2, S2)

    # print(p, q, r, s)
    # print(P, Q, R, S)
    # print(P2, Q2, R2, S2)
    # print("----------")

    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)


# Optimized solution
N = int(eval(input()))
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0
p = 0
q = 1
r = N // 2
s = r + 1
for r in range(2, N - 1):
    # 左
    P1, Q1 = P2, Q2 = -1, -1
    low, high = 1, r - 1
    while low + 1 < high:
        mid = (low + high) // 2
        P = SUM[mid - 1]
        Q = SUM[r - 1] - SUM[mid - 1]
        if P < Q:
            low = mid
        else:
            high = mid
    P1, Q1 = SUM[low - 1], SUM[r - 1] - SUM[low - 1]
    P2, Q2 = SUM[high - 1], SUM[r - 1] - SUM[high - 1]
    left_min, left_max = min(P1, Q1), max(P1, Q1)
    if abs(Q1 - P1) > abs(Q2 - P2):
        left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右
    R1, S1 = R2, S2 = -1, -1
    low, high = r + 1, N - 1
    while low + 1 < high:
        mid = (low + high) // 2
        R = SUM[mid - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[mid - 1]
        if R < S:
            low = mid
        else:
            high = mid
    R1, S1 = SUM[low - 1] - SUM[r - 1], SUM[N - 1] - SUM[low - 1]
    R2, S2 = SUM[high - 1] - SUM[r - 1], SUM[N - 1] - SUM[high - 1]
    right_min, right_max = min(R1, S1), max(R1, S1)
    if abs(R1 - S1) > abs(R2 - S2):
        right_min, right_max = min(R2, S2), max(R2, S2)

    # print(P1, Q1, R1, S1, sum([P1, Q1, R1, S1]), sum(A))
    # print(P2, Q2, R2, S2, sum([P2, Q2, R2, S2]), sum(A))
    # print("--------")
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)
# Original solution
#102_D
N = int(eval(input()))
A = [int(i) for i in input().split()]
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)
#尺取り法
Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs((Sum_L - AS[L]) - AS[L]) > abs((Sum_L - AS[L+1]) - AS[L+1]):
        L += 1

    while abs((AS[N-1]-AS[R]) - (AS[R]-Sum_L)) > abs((AS[N-1]-AS[R+1]) - (AS[R+1]-Sum_L)):
        R += 1
    P = AS[L]
    Q = Sum_L-AS[L]
    S = AS[R]-Sum_L
    T = AS[N-1]-AS[R]
    #print(Mid,L,R,abs(max(P,Q,S,T)-min(P,Q,S,T)))
    Ans = min(Ans, abs(max(P, Q, S, T)-min(P, Q, S, T)))
print(Ans)


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

Total_list = []
s = 0
for num in A_list:
  s += num
  Total_list.append(s)

L = 0
R = 2
ans = Total_list[N-1]+1
for Mid in range(1, N-2):
  sum_L = Total_list[Mid]
  sum_R = Total_list[N-1] - sum_L

  while abs(sum_L - 2*Total_list[L]) > abs(sum_L - 2*Total_list[L+1]):
    L += 1
  
  while abs((Total_list[N-1]-Total_list[R])-(Total_list[R] - sum_L)) > abs((Total_list[N-1]-Total_list[R+1])-(Total_list[R+1] - sum_L)):
    R += 1
  
  P = Total_list[L]
  Q = sum_L - Total_list[L]
  S = Total_list[R] - sum_L
  T = Total_list[N-1] - Total_list[R]

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

print(ans)
# Original solution
from itertools import *
n=int(eval(input()))
sumA=[0]+list(accumulate(list(map(int,input().split()))))
def check(l,m,r):
    if m==r:return False
    tmp=sumA[r]+sumA[l]
    return abs(tmp-sumA[m+1]*2)<abs(tmp-sumA[m]*2)
res=float('inf')
li,ri=1,3
for mid in range(2,n-1):
    while check(0,li,mid):li+=1
    while check(mid,ri,n):ri+=1
    x=sorted([sumA[li],sumA[mid]-sumA[li],sumA[ri]-sumA[mid],sumA[n]-sumA[ri]])
    tmp=x[3]-x[0]
    if tmp<res:res=tmp
print(res)

# Optimized solution
from itertools import *
eval(input())
s=list(accumulate(list(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)
# Original solution
def run(n, a):
    sum_a = [sum(a[0:i+1]) for i in range(n)]
    ret = sum_a[n - 1]
    for i in range(2, n-1):
        j_l = search_j(sum_a[: i], 0)
        j_r = search_j(sum_a[i:], sum_a[i - 1]) + i
        p = sum_a[j_l]
        q = sum_a[i - 1] - p
        r = sum_a[j_r] - q - p
        s = sum_a[n - 1] - r - q - p
        diff = max(p, q, r, s) - min(p, q, r, s)
        if ret > diff:
            ret = diff
    return ret


def search_j(sum_a, before):
    n = len(sum_a)
    sum_l = sum_a[0] - before
    sum_r = sum_a[n - 1] - sum_a[0]
    diff1 = sum_r - sum_l
    ret = 0
    for i in range(n - 1):
        sum_l = sum_a[i] - before
        sum_r = sum_a[n - 1] - sum_a[i]
        diff2 = sum_r - sum_l
        if diff2 < 0:
            if abs(diff1) < abs(diff2):
                return i - 1
            else:
                return i
        else:
            diff1 = diff2
            ret = i
    return ret


def read_line():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print((run(n, a)))


if __name__ == '__main__':
    main()


# Optimized solution
from itertools import accumulate


def run(n, a):
    # sum_a = [sum(a[0:i+1]) for i in range(n)]
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    # 真ん中の切れ込みを順に変更
    # 左の切れ込みの位置はiに対して単調増加
    # 左の切れ込みで真ん中の項を移動するかどうかは、
    # 真ん中の項を除いて、小さい方に入れる
    # ただし単調増加なので、左の切れ込みの左側が
    # 小さいときに真ん中を左の切れ込みの左側に入れる
    # 右も同様に考える
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff


def read_line():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print((run(n, a)))


if __name__ == '__main__':
    main()
# Original solution
from collections import deque
import bisect

n = int(eval(input()))
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
l, r = deque([b[1]]), deque(b[3 : n])
lenl, lenr = len(l), len(r)
ans = 1145141919810
for i in range(2, n - 1):
    cl, cr = b[i] / 2, (b[n] - b[i]) / 2
    ml = bisect.bisect_left(l, cl)
    mr = bisect.bisect_left(r, cr + b[i])
    if ml == 0:
        x = b[1]
    elif ml == lenl:
        x = l[-1]
    else:
        if l[ml] - cl <= cl - l[ml - 1]:
            x = l[ml]
        else:
            x = l[ml - 1]
    if mr == 0:
        y = r[0]
    elif mr == lenr:
        y = b[-2]
    else:
        if r[mr] - (cr + b[i]) <= (cr + b[i]) - r[mr - 1]:
            y = r[mr]
        else:
            y = r[mr - 1]
    s = [x, b[i] - x, y - b[i], b[n] - y]
    ans = min(ans, max(s) - min(s))
    l.append(b[i])
    r.popleft()
    lenl += 1
    lenr -= 1
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
    while True:
        if i == j + 1:
            x[i - 2][0] = b[j]
            break
        if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
            j += 1
        else:
            x[i - 2][0] = b[j]
            break
j = n - 1
for i in range(n - 2, 1, -1):
    while True:
        if i == j - 1:
            x[i - 2][1] = b[j]
            break
        if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
            j -= 1
        else:
            x[i - 2][1] = b[j]
            break
ans = 1145141919810
for i in range(n - 3):
    s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
    ans = min(ans, max(s) - min(s))
print(ans)