CodeEff/ECCO huggingface dataset:
# Original solution
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in range(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
ans = 8
def dfs(p, cnt, f):
    global ans
    if cnt>ans:
        return
    if is_correct(p):
        ans = cnt
        return
    for k in range(4):
        if k==f:
            continue
        rotate(p, k)
        dfs(p, cnt+1, k)
        rotate(p, k)

n = eval(input())
for _ in range(n):
    p = list(map(int, input().split()))
    ans = 8
    dfs(p, 0, -1)
    print(ans)

# Optimized solution
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in range(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
ans = 8
def dfs(p, cnt, f):
    global ans
    if ans<=cnt:
        return
    if is_correct(p):
        ans = cnt
        return
    for k in range(4):
        if ans<=cnt+1:
            break
        if k==f:
            continue
        rotate(p, k)
        dfs(p, cnt+1, k)
        rotate(p, k)

n = eval(input())
for _ in range(n):
    p = list(map(int, input().split()))
    ans = 8
    dfs(p, 0, -1)
    print(ans)
# Original solution
while 1:
    n=int(eval(input()))
    if n==0:break
    a=0
    for i in range(1,n//2):a+=(n+2*i-1)//(2*i)-1
    print((8*(2*n-1+a)))

# Optimized solution
while 1:
    n=int(eval(input()))
    if n==0:break
    a=0;i=1;b=n//2
    while i*i<b:a+=((b-1)//i+1)-i-1;i+=1
    a=(a+b-1)*2+i
    print((8*(a+n)))
# Original solution
x, t = (int(x) for x in input().split())

if x > t:
    ans = x-t
else:
    ans = 0
print(ans)

# Optimized solution
x, t = list(map(int, input().split()))
f = lambda x: x if x > 0 else 0
print((f(x-t)))
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

X,t = MI()
print((max(0,X-t)))


# Optimized solution
import sys
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))

X,t = MI()
print((max(0,X-t)))
# Original solution
a,b=list(map(int,input().split()));print((max(0,a-b)))

# Optimized solution
x,t=list(map(int,input().split()))
print((max(0,x-t)))
# Original solution
import sys
x, t = (int(i) for i in sys.stdin.readline().split())
print((x - t if x > t else 0))

# Optimized solution
import sys

def main():
    X, t = list(map(int, sys.stdin.readline().split()))
    ans = max(0, X - t)
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
a,b = list(map(int,input().split()))
print((max(a-b,0)))

# Optimized solution
def main():
    x,t = list(map(int,input().split()))
    print((max(0,x-t)))

if __name__ == '__main__':
    main()
# Original solution
X, t = list(map(int, input().split()))
print((max(X - t, 0)))

# Optimized solution
X, t = list(map(int, input().split()))
print((max(0, X - t)))
# Original solution
x,t=list(map(int, input().split()))

if x-t>0:
  print((int(x-t)))
else:
  print((int(0)))

# Optimized solution
x,t=list(map(int, input().split()))

A=x-t

if A>=0:
  print(A)
else:
  print((0))
# Original solution
X, t = list(map(int, input().split()))
print((max(X - t, 0)))

# Optimized solution
X, t = list(map(int, input().split()))
if X > t:
    print((X -t))
else:
    print((0))
# Original solution
x,t=list(map(int,input().split()))
print(("0" if x-t<0 else x-t))

# Optimized solution
print((max(eval(input().replace(" ","-")),0)))
# Original solution
print((max(0,eval(input().replace(' ','-')))))

# Optimized solution
print((max(eval(input().replace(*' -')),0)))
# Original solution
x, t = list(map(int, input().split()))
print((max(0, x - t)))


# Optimized solution
x, t = list(map(int, input().split()))
print((max(x - t, 0)))
# Original solution
x,t=list(map(int,input().split()))
print((0 if x<=t else x-t))

# Optimized solution
x,t=list(map(int,input().split()))
print(("0" if x-t<0 else x-t))
# Original solution
X,t=list(map(int,input().split()))

if (X-t)<0:
	print("0")
else:
	print((X-t))



# Optimized solution
X,t=list(map(int,input().split()))

print((max(X-t,0)))
# Original solution
class RangeMaximumQuery:
    def __init__(self, n):
        self.size = n
        self.dat = [0] * (2 * n - 1)
    
    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            d1 = self.dat[i * 2 + 1]
            d2 = self.dat[i * 2 + 2]
            if d1 > d2:
                self.dat[i] = d1
            else:
                self.dat[i] = d2
    
    def getmax(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.getmax(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.getmax(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl > vr:
                return vl
            else:
                return vr

def solve():
    from math import ceil, log
    
    n = int(eval(input()))
    A = list(map(int, input().split()))
    s = 2 ** ceil(log(n, 2))
    W = RangeMaximumQuery(s)
    for a_i in A:
        cost = W.getmax(0, a_i - 1, 0, 0, s) + a_i
        W.update(a_i - 1, cost)
    ans = n * (n + 1) // 2 - W.getmax(0, n, 0, 0, s)
    print(ans)

solve()


# Optimized solution
def solve():
    n = int(eval(input()))
    dp = [0] * (n + 1)
    
    def update(i, x):
        while i <= n:
            if dp[i] < x:
                dp[i] = x
            i += i & -i
    
    def get_sum(i):
        s = 0
        while i > 0:
            t = dp[i]
            if s < t:
                s = t
            i -= i & -i
        return s
    
    A = list(map(int, input().split()))
    
    for a_i in A:
        update(a_i, get_sum(a_i - 1) + a_i)
    
    ans = n * (n + 1) // 2 - get_sum(n)
    print(ans)

solve()
# Original solution
from itertools import accumulate
N=int(eval(input()))
t=[]
s=list(map(int,input().split()))
for i in range(2,N-1):
    p=10**9
    for j in range(1,len(s[:i])):
        a=sum(s[:i][:j])
        b=sum(s[:i][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x,y)=(a,b)
    p=10**9        
    for j in range(1,len(s[i:])):
        a=sum(s[i:][:j])
        b=sum(s[i:][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x1,y1)=(a,b)
    l=(x,y,x1,y1)
    t.append(max(l)-min(l))
print((min(t)))    

# Optimized solution
from itertools import accumulate
N=int(eval(input()))
s=list(accumulate(list(map(int,input().split()))))
ans=10**9
p=0
q=2
for i in range(2,N-1):
    while p<i-1 and abs(s[i-1]-2*s[p+1])<abs(s[i-1]-2*s[p]):
        p+=1
    if q<i:
        q+=1
    while q<N and abs(s[i-1]-2*s[q+1]+s[-1])<abs(s[i-1]-2*s[q]+s[-1]):   
        q+=1
    t=[s[q]-s[i-1],s[-1]-s[q],s[p],s[i-1]-s[p]]
    w=max(t)-min(t)
    ans=min(ans,w) 
print(ans)
# Original solution
from itertools import accumulate
N=int(eval(input()))
s=list(accumulate(list(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)    

# Optimized solution
from itertools import accumulate
N=int(eval(input()))
s=list(accumulate(list(map(int,input().split()))))
def f(N,s):
    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)
    return 
f(N,s)
# Original solution
from itertools import accumulate
from bisect import bisect_left
N = int(eval(input()))
A = list(map(int, input().split()))
A = list(accumulate(A))

ans = float('inf')
# 切る位置を全探索
for mid in range(2, N - 1):
    L, R = A[:mid], A[mid:]
    L_target, R_target = L[-1] / 2, (L[-1] + R[-1]) / 2
    L_index, R_index = bisect_left(L, L_target), bisect_left(R, R_target)

    if abs(L[L_index - 1] - L_target) < abs(L[L_index] - L_target):
        L_index -= 1
    if abs(R[R_index - 1] - R_target) < abs(R[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = L[L_index], L[-1]-L[L_index], R[R_index]-L[-1], R[-1]-R[R_index]
    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
N = int(eval(input()))
A = list(map(int, input().split()))
A = list(accumulate(A))

ans = float('inf')
# 切る位置を全探索
for mid in range(1, N):
    L_target, R_target = A[mid] // 2, (A[mid] + A[-1]) // 2
    L_index, R_index = bisect_left(A, L_target), bisect_left(A, R_target)
    if abs(A[L_index - 1] - L_target) < abs(A[L_index] - L_target):
        L_index -= 1
    if abs(A[R_index - 1] - R_target) < abs(A[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = A[L_index], A[mid]-A[L_index], A[R_index]-A[mid], A[-1]-A[R_index]
    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()))

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

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        if S[a_before] > S[b] - S[a_before]:
                a=a_before
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                if abs(S[b]-S[i-1]-S[i-1]) < abs(S[b]-S[i]-S[i]):
                                        a=i-1
                                        a_before = i-1
                                        break
                                else:
                                        a=i
                                        a_before = i
                                        break
                else:
                        a=b-1
                        a_before = b-1

        if S[c_before] - S[b] > S[N] - S[c_before]:
                c=c_before
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                if abs((S[N]-S[i-1]) - (S[i-1]-S[b])) < abs((S[N]-S[i]) - (S[i]-S[b])):
                                        c=i-1
                                        c_before = i-1
                                        break
                                else:
                                        c=i
                                        c_before = i
                                        break
                else:
                        c=N-1
                        c_before = N-1

        ans_tmp.append(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((min(ans_tmp)))

# Optimized solution
N = int(eval(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_tmp = []
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_tmp.append(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((min(ans_tmp)))
# Original solution
#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_left(B, B[N - 1] / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = B[N - 1] - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = B[N - 1] / 2 - min_d
    max_half = B[N - 1] / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(B[N - 1] - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != B[N - 1] + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = B[N - 1] - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()



# Optimized solution
#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()
# Original solution
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(eval(input()))
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

# Optimized solution
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(eval(input()))
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs, cs[m] // 2, hi = m)
  r = bl(cs, cs[m] + (cs[-1] - cs[m]) // 2, lo = m)
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)
# Original solution
import itertools

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

lst_accum = list(itertools.accumulate(lst))

def shaku(lst_accum, first):
    all_sum = lst_accum[-1]
    min_diff = 10**100
    for k in range(len(lst_accum)-1):
        diff = abs(all_sum - 2*lst_accum[k] + first)
        if min_diff > diff:
            index = k
            min_diff = diff
            P = lst_accum[k] - first
    return P, all_sum - P - first

min_diff = 10**100
for k in range(1, len(lst_accum)-2):
    lst_first = lst_accum[:k+1]
    lst_second = lst_accum[k+1:]
    #print('length_first: ', len(lst_first))
    P, Q = shaku(lst_first, 0)
    #print('length_second: ', len(lst_second))
    R, S = shaku(lst_second, lst_accum[k])
    min_diff = min(min_diff, max(P, Q, R, S) - min(P, Q, R, S))
print(min_diff)

# Optimized solution
import itertools

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

lst_accum = list(itertools.accumulate(lst))

min_diff = 10**100
first_cut = 0
third_cut = 2
all_sum = lst_accum[-1]
for k in range(1, len(lst_accum)-2):
    second_last = lst_accum[k]
    P = lst_accum[first_cut]
    Q = second_last - P
    diff = abs(P-Q)
    while k - first_cut > 1 and diff > abs(second_last - lst_accum[first_cut+1]*2):
        first_cut += 1
        P = lst_accum[first_cut]
        Q = second_last - P
        diff = abs(P-Q)    
    
    if third_cut == k:
        third_cut += 1
    third_last = lst_accum[third_cut]
    S = all_sum - third_last
    R = third_last - second_last
    diff = abs(S-R)
    while (n-1) - third_cut > 1 and diff > abs(all_sum - lst_accum[third_cut+1]*2 + second_last):
        third_cut += 1
        third_last = lst_accum[third_cut]
        S = all_sum - third_last
        R = third_last - second_last
        diff = abs(S-R)
    
    #print(first_cut, k, third_cut)
    min_diff = min(min_diff, max(P,Q,R,S) - min(P,Q,R,S))
    #print(min_diff)
    

print(min_diff)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    bl = [True, True]
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if not bl[0]:
            break
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
        else:
            bl[0] = False
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if not bl[1]:
            break
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
        else:
            bl[1] = False
    ans = min(ans, max(ex) - min(ex))

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline


def main():
    n = int(eval(input()))
    A = list(map(int, input().split()))
    F = [int()] * n
    F[0] = A[0]
    for b in range(1, n):
        F[b] = F[b - 1] + A[b]

    res = [0]*4
    data = [10 ** 18] * 2
    ex = [0]*4
    ans = 10 ** 18
    s = 0
    t = 2
    for i in range(1, n - 2):
        bl = [True, True]
        for j in range(s, i):
            res[0] = F[j]
            res[1] = F[i] - F[j]
            if not bl[0]:
                break
            if data[0] > abs(res[1] - res[0]) or j == s:
                s = j
                ex[0] = res[0]
                ex[1] = res[1]
                data[0] = abs(res[1] - res[0])
            else:
                bl[0] = False
        for k in range(t, n):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            if not bl[1]:
                break
            if data[1] > abs(res[3] - res[2]) or k == t:
                t = k
                ex[2] = res[2]
                ex[3] = res[3]
                data[1] = abs(res[3] - res[2])
            else:
                bl[1] = False
        ans = min(ans, max(ex) - min(ex))
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
INF = float('inf')
from bisect import bisect
N = int(eval(input()))
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-1):
    l = S[:i]
    r = S[i:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,len(l)-2)}:
        for q in {k-1,min(k,len(r)-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)


# Optimized solution
INF = float('inf')
from bisect import bisect
N = int(eval(input()))
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-1):
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,i,min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)