CodeEff/ECCO huggingface dataset:
# Original solution
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 2, cut + 3):
    if head <= i < end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if score > abs(a - b):
        score = abs(a - b)
        reta, retb = a, b
  return (reta, retb)

n = int(eval(input()))
acc = [0]
acc += accumulate(list(map(int, input().split())))

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

# Optimized solution
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 1, cut + 2):
    if head <= i < end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if score > abs(a - b):
        score = abs(a - b)
        reta, retb = a, b
  return (reta, retb)

n = int(eval(input()))
acc = [0]
acc += accumulate(list(map(int, input().split())))

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

cumsum = [a[0]]
for i in range(1, n):
    cumsum.append(cumsum[i-1] + a[i])

i, k = 0, 2
ans = 10**18
for j in range(1, n-2):
    while i < j:
        p = cumsum[i]
        q = cumsum[j] - cumsum[i]
        p_new = cumsum[i+1]
        q_new = cumsum[j] - cumsum[i+1]
        if abs(q_new - p_new) > abs(q - p):
            break
        else:
            i += 1

    while k < n-1:
        r = cumsum[k] - cumsum[j]
        s = cumsum[n-1] - cumsum[k]
        r_new = cumsum[k+1] - cumsum[j]
        s_new = cumsum[n-1] - cumsum[k+1]
        if abs(s_new - r_new) > abs(s - r):
            break
        else:
            k += 1

    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
 
i, k = 0, 2
p, q, r, s = 0, a[0], a[1], sum(a[2:])
ans = sum(a)
for j in range(1, n-2):
    q += a[j]
    while abs((q-a[i]) - (p+a[i])) < abs(q - p):
        p += a[i]
        q -= a[i]
        i += 1
 
    r -= a[j]
    while abs((s-a[k]) - (r+a[k])) < abs(s - r):
        r += a[k]
        s -= a[k]
        k += 1
 
    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    # print(i, j, k, ans, pqrs)
    
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(b[i]+c[-i-1])
    y = min(b[i]+c[-i-1])
    r = min(r, x-y)
print(r)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
def f(a):
    l, r = a[:2]
    m = 1
    b = [(l,r)]
    for i in range(2, n-2):
        r += a[i]
        while m<i and abs(l-r)>abs(l-r+a[m]*2): 
            l, r = l+a[m], r-a[m]
            m += 1
        b.append((l,r))
    return b
print((min(max(p,q,r,s)-min(p,q,r,s)
        for ((p,q),(r,s)) in zip(f(a), f(a[::-1])[::-1]))))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
from bisect import bisect

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
from bisect import bisect

# 区間の和を高速に求めたいので累積和
S = [0]*N
S[0] = A[0]
for i in range(1,N):
    S[i] = S[i-1]+A[i]

Ans = 10**15
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ax = S[i-1]/2
    ai = bisect(S,ax)
    if abs(S[ai-1]-ax) < abs(S[ai]-ax):
        ai -= 1
    bx = (S[N-1]+S[i-1])/2
    bi = bisect(S,bx)
    if abs(S[bi-1]-bx) < abs(S[bi]-bx):
        bi -= 1
    x1,x2,x3,x4 = S[ai],S[i-1]-S[ai],S[bi]-S[i-1],S[N-1]-S[bi]
    # 考慮した組み合わせで最小のものを記録
    Ans = min(Ans,max(x1,x2,x3,x4)-min(x1,x2,x3,x4))

print(Ans)
# Original solution
import bisect

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 = 10**20
for i in range(2, N-1):
    m = bisect.bisect(S[:i], S[:i][-1]//2)

    if m == 0:
        L = [S[:i][0], S[:i][-1]-S[:i][0]]
    else:
        L = [S[:i][m], S[:i][-1]-S[:i][m]]
        L2 = [S[:i][m-1], S[:i][-1]-S[:i][m-1]]

        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    m = bisect.bisect(S[i:], (S[i:][-1]+S[:i][-1])//2)
    if m == 0:
        R = [S[i:][0]-S[:i][-1], S[i:][-1]-S[i:][0]]
    else:
        R = [S[i:][m]-S[:i][-1], S[i:][-1]-S[i:][m]]
        R2 = [S[i:][m-1]-S[:i][-1], S[i:][-1]-S[i:][m-1]]

        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2

    #print(L, end="")
    #print(R)

    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

print(ans)



# Optimized solution
import bisect

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 = 1e18
for i in range(2, N-1):
    # 左側 [0,i)
    left_sum = S[i-1]
    m = bisect.bisect(S, left_sum/2)

    L = [S[m], left_sum-S[m]]

    if m != 0:
        L2 = [S[m-1], left_sum - S[m-1]]
        if(abs(L[0]-L[1]) > abs(L2[0]-L2[1])): L = L2

    # 右側 [i,N)
    m = bisect.bisect(S, (S[-1]+left_sum)/2)
    R = [S[m]-left_sum, S[-1]-S[m]]

    if m != i:
        R2 = [S[m-1]-left_sum, S[-1]-S[m-1]]
        if(abs(R[0]-R[1]) > abs(R2[0]-R2[1])): R = R2


    ans = min(ans, max(L[0],L[1],R[0],R[1]) - min(L[0],L[1],R[0],R[1]))

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

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

accAs = [0] + list(accumulate(As))

# As[iFr]～As[iTo]の和を求める
def getSum(iFr, iTo):
    return accAs[iTo+1] - accAs[iFr]


# As[iFr]～As[iTo]を前後半の総和の差が最小となるように分解する
def getDivision(iFr, iTo):
    sumB = getSum(iFr, iTo)
    iMid = bisect_right(accAs, accAs[iFr]+sumB/2, iFr+1, iTo+2) - 1

    diff1, diff2 = float('inf'), float('inf')
    if iMid != iFr:
        sum1L = getSum(iFr, iMid-1)
        sum1R = getSum(iMid, iTo)
        diff1 = abs(sum1L - sum1R)
    if iMid != iTo:
        sum2L = getSum(iFr, iMid)
        sum2R = getSum(iMid+1, iTo)
        diff2 = abs(sum2L - sum2R)

    return [sum1L, sum1R] if diff1 <= diff2 else [sum2L, sum2R]


# 真ん中の区切りを全通り試す
ans = float('inf')
for iMid in range(1, N-3+1):
    sumD = []
    sumD += getDivision(0, iMid)
    sumD += getDivision(iMid+1, N-1)

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

print(ans)


# Optimized solution
N = int(eval(input()))
As = list(map(int, input().split()))

ans = float('inf')
iB, iD = 1, 3
(P, Q, R), S = As[:3], sum(As[3:])

# 真ん中の区切りを全通り試す
for iC in range(2, N - 1):
    while P < Q and As[iB] <= Q - P:
        P += As[iB]
        Q -= As[iB]
        iB += 1

    while R < S and As[iD] <= S - R:
        R += As[iD]
        S -= As[iD]
        iD += 1

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

    Q += As[iC]
    R -= As[iC]

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

N = int(eval(input()))
C = [0]+list(accumulate(list(map(int,input().split()))))

def helper(i,j):
  m = (C[j]+C[i])/2
  k = bisect_left(C, m, lo=i+1,hi=j-1)

  if k > i+1:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]
  return a,b


m = bisect_left(C,C[N]/2)
if m < 2:
  m = 2
elif m > N-2:
  m = N-2

L = helper(0,m)+helper(m,N)
best = max(L)-min(L)

i = m+1
while i < N-1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i += 1

i = m-1
while i > 1 and abs(abs(C[N]-C[i])-abs(C[i])) < best*2:
  L = helper(0,i)+helper(i,N)
  best = min(best, max(L)-min(L))
  i -= 1


print(best)

# Optimized solution
from itertools import accumulate
from bisect import bisect

N = int(eval(input()))
C = [0]+list(accumulate(list(map(int,input().split()))))

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

def solve(x):
  L = h(0,x)+h(x,N)
  return max(L)-min(L)

print((min(solve(i) for i in range(2,N-1))))
# Original solution
from itertools import accumulate
from bisect import bisect

N = int(eval(input()))
C = [0]+list(accumulate(list(map(int,input().split()))))
S = C[N]

def solve(x):
  cx = C[x]
  k = bisect(C, cx//2, lo=1,hi=x)
  _,a,b = min((abs(cx-2*c),cx-c,c) for c in (C[k-1],C[k]))
  k = bisect(C, (S+cx)//2, lo=x+1,hi=N)
  _,c,d = min((abs(cx+S-2*c),S-c,c-cx) for c in (C[k-1],C[k]))
  L = (a,b,c,d)
  return max(L)-min(L)

print((min(solve(i) for i in range(2,N-1))))

# Optimized solution
from itertools import accumulate
from bisect import bisect

N = int(eval(input()))
C = [0]+list(accumulate(list(map(int,input().split()))))
S = C[N]

def it():
  k1 = 1
  k2 = 3
  for i in range(2,N-1):
    ci = C[i]
    k1 = bisect(C, ci//2, lo=k1,hi=i)
    _,a,b = min((abs(ci-2*c),ci-c,c) for c in (C[k1-1],C[k1]))
    k2 = bisect(C, (S+ci)//2, lo=k2,hi=N)
    _,c,d = min((abs(ci+S-2*c),S-c,c-ci) for c in (C[k2-1],C[k2]))
    yield max(a,b,c,d)-min(a,b,c,d)

print((min(it())))
# Original solution
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    p=aa[0]
    q=aa[1]
    j=1
    dl=abs(p-q)
    k=3
    r=aa[2]
    s=sum(aa[3:])
    dr=abs(r-s)
    while abs(r-s+aa[k]*2)<dr:
        r+=aa[k]
        s-=aa[k]
        dr=abs(r-s)
        k+=1
    ans=max(p,q,r,s)-min(p,q,r,s)
    for i in range(3,n-1):
        q += aa[i - 1]
        dl = abs(p - q)
        while abs(p - q + aa[j] * 2) < dl:
            p += aa[j]
            q -= aa[j]
            dl = abs(p - q)
            j += 1

        r -= aa[i - 1]
        dr = abs(r - s)
        while abs(r-s+aa[k]*2)<dr:
            r+=aa[k]
            s-=aa[k]
            dr=abs(r-s)
            k+=1
        cur=max(p,q,r,s)-min(p,q,r,s)
        if cur<ans:ans=cur
    print(ans)

main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    n=II()
    aa=LI()

    pre=[0]*(n+1)
    for i in range(n):pre[i+1]+=pre[i]+aa[i]

    ll=[[0]*2 for _ in range(n)]
    rr=[[0]*2 for _ in range(n)]
    j=1
    for i in range(2,n-1):
        while j<i-1 and pre[i]-pre[j]*2>0:j+=1
        if pre[i]-pre[j-1]*2<-pre[i]+pre[j]*2:j-=1
        ll[i][0]=min(pre[i]-pre[j],pre[j])
        ll[i][1]=max(pre[i]-pre[j],pre[j])
    j=n-1
    for i in range(n-2,1,-1):
        while j>i+1 and pre[n]+pre[i]-pre[j]*2<0:j-=1
        if -pre[n]-pre[i]+pre[j+1]*2<pre[n]+pre[i]-pre[j]*2:j+=1
        rr[i][0]=min(pre[n]-pre[j],pre[j]-pre[i])
        rr[i][1]=max(pre[n]-pre[j],pre[j]-pre[i])
    #print(ll,rr)

    ans=10**16
    for i in range(2,n-1):
        mn=min(ll[i][0],rr[i][0])
        mx=max(ll[i][1],rr[i][1])
        cur=mx-mn
        if cur<ans:ans=cur
    print(ans)

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

ans = []
for _ in range(2, N-1):
    p = A[:_]
    q = A[_:]
    P = sum(p)
    Q = sum(q)
    p_sa = 10**15
    q_sa = 10**15
    for i in range(1,len(p)):
        s = sum(p[:i])
        sa = abs(P-s*2)
        if sa < p_sa:
            n = [s,P-s]
            p_sa = sa
    for i in range(1,len(q)):
        s = sum(q[:i])
        sa = abs(Q - s*2)
        if sa < q_sa:
            m = [s,Q-s]
            q_sa = sa
    ans.append(max(n+m)-min(n+m))
print((min(ans)))

# Optimized solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(1, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
print((min(ans)))
# Original solution
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


# import numpy as np
import bisect
n = int(eval(input()))
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
# ca = a.cumsum()

def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)

# Optimized solution
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(eval(input()))
a = list(map(int, input().split()))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s

diff = [None] * n

s = 0
t = 1
v1 = 0 # a[:s]
v2 = a[0] # sum(a[s:t])
diff[t-1] = (v1,v2)
while t<n:
#     print(t, v1-v2)
    t += 1
    v2 += a[t-1]
    while v1<v2 and s<t:
        if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
            diff[t-1] = (v1,v2)
        s += 1
        v1 += a[s-1]
        v2 -= a[s-1]
    if diff[t-1] is None or abs(v1-v2)<abs(diff[t-1][0] - diff[t-1][1]):
        diff[t-1] = (v1,v2)        
    if v1>v2 and s>=1:
        v1 -= a[s-1]
        v2 += a[s-1]
        s -= 1

diff2 = [None] * n

s = n
t = n-1
v1 = 0 # sum(a[s:])
v2 = a[-1] # sum(a[t:s])
diff2[t] = (v1,v2)
while t>=1:
    # print(t, v1, v2)
    t -= 1
    v2 += a[t]
    while v1<v2 and s>t:
        if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
            diff2[t] = (v1,v2)
        s -= 1
        v1 += a[s]
        v2 -= a[s]
    if diff2[t] is None or abs(v1-v2)<abs(diff2[t][0] - diff2[t][1]):
        diff2[t] = (v1,v2)        
    if v1>v2 and s<=n-2:
        v1 -= a[s]
        v2 += a[s]
        s += 1
print((min((max(diff[i][0], diff[i][1],diff2[i+1][0],diff2[i+1][1]) - min(diff[i][0], diff[i][1],diff2[i+1][0],diff2[i+1][1])) for i in range(n-1))))
# Original solution
def main():
    from itertools import accumulate, product

    def binary_search(a, x, lo, hi):
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    n = int(eval(input()))
    *a, = list(map(int, input().split()))
    acc = (0,) + tuple(accumulate(a))

    # [0,i), [i,j), [j,k), [k, n)

    ret = acc[-1]
    for j in range(2, n - 1):
        left = acc[j]
        right = acc[-1] - left

        i = binary_search(acc, left // 2, 2, j + 2)
        k = binary_search(acc, left + (right // 2), j + 2, n + 1)

        li = i - 1, i
        rk = k - 1, k

        for i, k in product(li, rk):
            if i <= 0 or k <= j:
                continue
            pqrs = acc[i], left - acc[i], acc[k] - left, acc[-1] - acc[k]
            ret = min(
                ret,
                max(pqrs) - min(pqrs)
            )

    print(ret)


if __name__ == '__main__':
    main()


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

    # [0,i), [i,j), [j,k), [k, n)
    tot = sum(a)
    ret = tot

    i, k = 1, 3
    p, q, r, s = a[0], a[1], a[2], tot - sum(a[:3])

    for j in range(2, n - 1):
        while (i + 1 < j) and (abs(p - q + a[i] * 2) < abs(p - q)):
            p += a[i]
            q -= a[i]
            i += 1

        while (k + 1 < n) and (abs(r - s + a[k] * 2) < abs(r - s)):
            r += a[k]
            s -= a[k]
            k += 1

        ret = min(ret, max(p, q, r, s) - min(p, q, r, s))

        q += a[j]
        r -= a[j]

    print(ret)


if __name__ == '__main__':
    main()
# Original solution
# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_max(arr):
    """リストの中を二つに分けて、総和の小さい方と大きい方を返す"""
    left = 0; right = len(arr)-1
    l_total = arr[left]
    r_total = arr[right]
    while left + 1 < right:
        if l_total <= r_total:
            left += 1
            l_total += arr[left]
        else:
            right -= 1
            r_total += arr[right]
    mi, ma = min(l_total, r_total), max(l_total, r_total)
    return mi, ma

answer = 10 ** 15
mid = N // 2
used = set([0, 1, N-1])

def F(l, mid, r):
    global answer, used
    used.add(mid)
    l_min, l_max = min_max(A[:mid])
    r_min, r_max = min_max(A[mid:])
    temp = max(l_max, r_max) - min(l_min, r_min)
    if temp < answer:
        answer = temp
    if l_min <= r_min:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)
    else:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    if l_max >= r_max:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    else:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)

F(0, mid, N-1)
print(answer)
# 08

# Optimized solution
# coding: utf-8
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  # 左のリストで2つに切り分けるindex
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
            diff = temp
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 17
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)
# 27r
# Original solution
def i1():
 return int(eval(input()))
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
c=[0 for i in range(n)]
b=sum(a)

for i in range(n):
 if i: c[i]+=c[i-1]
 c[i]+=a[i]
f=float("inf")
import bisect
e=[]
b=a[0]
d=c[n-1]-c[0]
for i in range(1,n-2):
 b+=a[i]
 d-=a[i]
 x=bisect.bisect_left(c[:i+1],b/2)
 
 if abs(c[i]-2*c[x])>abs(c[i]-2*c[x-1]) and x>0:
   e.append(c[i]-c[x-1])
   e.append(c[x-1])
 else:
   e.append(c[i]-c[x])
   e.append(c[x])
 y=bisect.bisect_left(c[i+1:],d/2+c[i])+i+1
 if abs(c[n-1]-c[y]-(c[y]-c[i]))>abs(c[n-1]-c[y-1]-(c[y-1]-c[i])) and y>0:
   e.append(c[n-1]-c[y-1])
   e.append(c[y-1]-c[i])
 else:
   e.append(c[n-1]-c[y])
   e.append(c[y]-c[i])

 f=min(f,max(e)-min(e))
 e=[]
print(f)

# Optimized solution
def i1():
 return int(eval(input()))
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
c=[0 for i in range(n)]


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

l=0
r=2
f=float("inf")
for i in range(1,n-1):
 while abs(c[l]-(c[i]-c[l]))>abs(c[l+1]-(c[i]-c[l+1])):
   l+=1
 while abs(c[r]-c[i]-(c[n-1]-c[r]))>abs(c[r+1]-c[i]-(c[n-1]-c[r+1])):
   r+=1
 e=[c[l],c[i]-c[l],c[r]-c[i],c[n-1]-c[r]]
 f=min(f,max(e)-min(e))
print(f)
# Original solution
n=int(eval(input()))
s=list(map(int,input().split()))
a=[0]
for _ in range(n):
    a.append(sum(s[:_+1]))

ans=10**9
f=1
g=3
for i in range(2,n-1):
    while f < i and abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while g < n and abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans=min(ans,max(ls)-min(ls))
print(ans)

# Optimized solution
n=int(eval(input()))
s=list(map(int,input().split()))
a=[0]
c=0
for si in s:
    c+=si
    a.append(c)
ans=[]
f=1
g=3
for i in range(2,n-1):
    while abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans.append(max(ls)-min(ls))
print((min(ans)))