CodeEff/ECCO huggingface dataset:
# Original solution
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
left = -1
ans=10e9

for mid in range(1,N-1):
	diffL=10e9
	diffR=10e9
	for l in range(mid):
		tmpP=SumA[l]
		tmpQ=SumA[mid] - SumA[l]
		if abs(tmpQ-tmpP) < diffL:
			diffL = abs(tmpQ-tmpP)
			left = l
			P=tmpP
			Q=tmpQ

	for r in range(mid+1,N-1):

		tmpR=SumA[r] - SumA[mid]
		tmpS=SumA[N-1] - SumA[mid] - tmpR
		if abs(tmpS-tmpR) < diffR:
			diffR = abs(tmpS-tmpR)
			right = r
			R=tmpR
			S=tmpS

	# print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)


# Optimized solution
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)
# Original solution
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)


# Optimized solution
# 整数列A 
# 3箇所で切って、４つに
# それぞれの総和の最大値と最小値の差の絶対値の最小値

# 中央を固定することを考える(結局、その固定を全検索するが)
# 中央固定後、左側について、両方が同じくらいの値になるのが最適と考えて良いらしい

from itertools import accumulate

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

tmpP=tmpQ=tmpR=tmpS=0
P=Q=R=S=0
ans=10e9
l = 0
r = 2

# midとmid+1の間が中間の切断
for mid in range(1,N-2):

	# l,rは、単調増加であるため、全ての中間点を求めるループの間、クリアの必要がないらしい

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while l < mid and abs((SumA[mid] - SumA[l+1])-SumA[l+1]) < abs((SumA[mid] - SumA[l])-SumA[l]):
		l += 1

	# 次のやつよりも、今のやつの方が大きい限り、継続
	# 必ず、それが逆転する時が最小のはず、という考え。。。
	while r < N-1 and abs((SumA[N-1]-SumA[r+1])-(SumA[r+1]-SumA[mid])) < abs((SumA[N-1] - SumA[r])-(SumA[r] - SumA[mid])):
		r += 1

	#print("{},{}".format(mid,l))

	P=SumA[l]
	Q=SumA[mid]-SumA[l]
	R=SumA[r]-SumA[mid]
	S=SumA[N-1]-SumA[r]

	#print(P,Q,R,S)
	diff=max(P,Q,R,S)-min(P,Q,R,S)
	diff=abs(diff)
	ans = min(ans,diff)

print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))

cut_1=1
cut_2=2
cut_3=3
A_0=A[:cut_1]
S_0=sum(A_0)

A_1=A[cut_1:cut_2]
S_1=sum(A_1)

A_2=A[cut_2:cut_3]
S_2=sum(A_2)

A_3=A[cut_3:]
S_3=sum(A_3)


def irekae(S,T,i):
    if abs(S-T)>abs((S-A[i-1])-(T+A[i-1])):
        
        S=S-A[i-1]
        T=T+A[i-1]
        i=i-1
        
    elif abs(T-S)>abs((T-A[i])-(S+A[i])):
        #print(T,S,T-S,i)
        S=S+A[i]
        T=T-A[i]
        i=i+1
        #print(T,S,T-S,i)

    return (S,T,i)

MIN=[]
cut_1b=0
cut_3b=0
for cut_2 in range(2,N-1):
    cut_1b=0
    cut_3b=0
    while cut_1b != cut_1:
        cut_1b=cut_1
        S_0,S_1,cut_1=irekae(S_0,S_1,cut_1)
        #print(cut_1)

    while cut_3b != cut_3:
        cut_3b=cut_3
        S_2,S_3,cut_3=irekae(S_2,S_3,cut_3)

    MIN+=[max([S_0,S_1,S_2,S_3])-min([S_0,S_1,S_2,S_3])]
    #print(cut_1,cut_2,cut_3,S_0,S_1,S_2,S_3)

    S_1+=A[cut_2]
    S_2-=A[cut_2]

print((min(MIN)))


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

SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)
    
i=1
j=2
k=3
P=SUM[i]
Q=SUM[j]-SUM[i]
R=SUM[k]-SUM[j]
S=SUM[N]-SUM[k]
ANS=10**10
check=1

while j<N-1:
    check=1
    while check==1:
        check=0
        if i<j-1:
            if abs(P-Q)>abs(P+A[i]-Q+A[i]):
                P+=A[i]
                Q-=A[i]
                i+=1
                check=1
        if k<N-1:

            if abs(R-S)>abs(R+A[k]-S+A[k]):
                R+=A[k]
                S-=A[k]
                k+=1
                check=1

    #print(P,Q,R,S,i,j,k)
    
    if ANS>max([P,Q,R,S])-min([P,Q,R,S]):
        ANS=max([P,Q,R,S])-min([P,Q,R,S])

    
    Q+=A[j]
    R-=A[j]
    j+=1

print(ANS)
# Original solution
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


def binary_search(A, x):
    low = 0
    high = len(A) - 1
    mid = (low + high) // 2

    while low <= high:
        if A[mid] == x:
            break
        elif A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high) // 2

    if mid < 0:
        return 0
    else:
        return mid


N = int(eval(input()))

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
for mid in range(2, N - 1):
    L = B[:mid]
    R = B[mid:]
    R = [R[i] - L[-1] for i in range(len(R))]
    # print(L)
    # print(R)

    sum_list = []
    for li in [L, R]:
        if len(li) == 2:  # R, Lの要素数が2の場合の分け方は1通り
            sum_list.append(li[0])
            sum_list.append(li[1] - li[0])
            continue

        # 真ん中の切れ込みが固定されている時のRとLの切れ込みの決定
        mid = binary_search(li, li[-1] // 2)

        diff1 = abs(2 * li[mid] - li[-1])
        diff2 = abs(2 * li[mid + 1] - li[-1])

        if diff1 < diff2:
            sum_list.append(li[mid])
            sum_list.append(li[-1] - li[mid])
        else:
            sum_list.append(li[mid + 1])
            sum_list.append(li[-1] - li[mid + 1])

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

print(ans)

# Optimized solution
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(eval(input()))

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)
# Original solution
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(eval(input()))

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)

# Optimized solution
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(eval(input()))

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while B[mid] > B[mid_l] + B[mid_l + 1]:
        mid_l += 1
    while t > B[mid_r] + B[mid_r + 1] - B[mid]:
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

    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()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
for i in range(3, N):#R[:i]とR[i:]に切る
  l, r = 2, i + 1
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(a, b, c, d, ans, ans2)
print(ans)
    
  
  

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
l, r = 2, 4
for i in range(3, N):#R[:i]とR[i:]に切る
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(R[l - 1], R[i - 1] - R[l - 1],R[r - 1] - R[i - 1], R[N] - R[r - 1], ans)
print(ans)
# Original solution
import math

n = int(eval(input()))
a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def bs(s, l, r, rr):
    if l == r:
        return l
    else:
        h = math.ceil((l + r) / 2)
        if s[h] * 2 > s[rr]:
            return bs(s, l, h - 1, rr)
        else:
            return bs(s, h, r, rr)
        
def min_2(s, i, rr):
    a = abs(s[i] - (s[rr] - s[i]))
    b = abs(s[i + 1] - (s[rr] - s[i + 1]))
    if a <= b:
        return i
    else:
        return i + 1
    
def f(a):
    return max(a) - min(a)

m_min = 2 * 10**14
for i in range(2, n - 1):
    pq = bs(s, 1, i, i)
    rs = bs(sr, 1, n - i, n - i)
    pq = min_2(s, pq, i)
    rs = min_2(sr, rs, n - i)
    m = f([s[pq], s[i] - s[pq], sr[rs], sr[n - i] - sr[rs]])
    if m < m_min:
        m_min = m
        
print(m_min)

# Optimized solution
import math

n = int(eval(input()))

a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)
li = 0
ri = n

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def f(a):
    return max(a) - min(a)

def fs(rr):
    global li
    while abs(s[rr] - 2 * s[li]) > abs(s[rr] - 2 * s[li + 1]):
        li += 1
        
def fsr(rr):
    global ri
    while abs(sr[rr] - 2 * sr[ri]) > abs(sr[rr] - 2 * sr[ri - 1]):
        ri -= 1

m_min = 2 * 10**14
for i in range(2, n - 1):
    fs(i)
    fsr(n - i)
    m = f([s[li], s[i] - s[li], sr[ri], sr[n - i] - sr[ri]])
    if m < m_min:
        m_min = m
        
print(m_min)
# Original solution
from itertools import accumulate
n=int(eval(input()))
a=list(map(int, input().split()))
acc=list(accumulate(a))
sumA=acc[-1]
cut=[0, 1, 2, len(a)-1]
score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
ans=max(score)-min(score)
for i in range(1,len(a)-1):
    cut[1]=i    
    while abs(acc[cut[1]]-acc[cut[0]]-acc[cut[0]]) > abs(acc[cut[1]]-acc[cut[0]+1]-acc[cut[0]+1]):
        cut[0]+=1 
    while abs(acc[cut[3]]-acc[cut[2]]-(acc[cut[2]]-acc[cut[1]])) > abs(acc[cut[3]]-acc[cut[2]+1]-(acc[cut[2]+1]-acc[cut[1]])):
        cut[2]+=1
    score=[acc[cut[0]], acc[cut[1]]-acc[cut[0]], acc[cut[2]]-acc[cut[1]], acc[cut[3]]-acc[cut[2]]]
    ans=min(ans, max(score)-min(score))

print(ans)


# Optimized solution
from itertools import accumulate
n=int(eval(input()))
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; right=2
ans=float('inf')
for center in range(1,n-1):
    while abs(acc[center]-acc[left]-acc[left]) > abs(acc[center]-acc[left+1]-acc[left+1]):
        left+=1 
    while abs(acc[n-1]-acc[right]-(acc[right]-acc[center])) > abs(acc[n-1]-acc[right+1]-(acc[right+1]-acc[center])):
        right+=1
    score=acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]
    ans=min(ans, max(score)-min(score))

print(ans)
# Original solution
from itertools import accumulate
n=int(eval(input()))
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; right=2
ans=float('inf')
for center in range(1,n-1):
    while abs(acc[center]-acc[left]-acc[left]) > abs(acc[center]-acc[left+1]-acc[left+1]):
        left+=1 
    while abs(acc[n-1]-acc[right]-(acc[right]-acc[center])) > abs(acc[n-1]-acc[right+1]-(acc[right+1]-acc[center])):
        right+=1
    score=acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]
    ans=min(ans, max(score)-min(score))

print(ans)


# Optimized solution
from itertools import accumulate
n=int(eval(input()))
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; center=1; right=2
ans=float('inf')
score=[acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]]
nextS=[acc[left+1], acc[center]-acc[left+1], acc[right+1]-acc[center], acc[n-1]-acc[right+1]]
for center in range(1,n-1):
    while abs(score[1]-score[0]) > abs(nextS[1]-nextS[0]):
        left+=1
        score[0]+=a[left]
        score[1]-=a[left]
        nextS[0]+=a[left+1]
        nextS[1]-=a[left+1]
    while abs(score[3]-score[2]) > abs(nextS[3]-nextS[2]):
        right+=1
        score[2]+=a[right]
        score[3]-=a[right]
        nextS[2]+=a[right+1]
        nextS[3]-=a[right+1]
    ans=min(ans, max(score)-min(score))
    score[1]+=a[center+1]
    score[2]-=a[center+1]
    nextS[1]+=a[center+1]
    nextS[2]-=a[center+1]
print(ans)
# Original solution
def min_diff(x, base=0):
    n = len(x)
    ok = - 1  # x[ok] - base < x[n - 1] - x[ok]
    ng = n - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if x[mid] - base < x[n - 1] - x[mid]:
            ok = mid
        else:
            ng = mid
    d_ok = abs((x[ok] - base) - (x[n - 1] - x[ok]))
    d_ng = abs((x[ng] - base) - (x[n - 1] - x[ng]))
    if d_ok < d_ng:
        return (x[ok] - base), (x[n - 1] - x[ok])
    else:
        return (x[ng] - base), (x[n - 1] - x[ng])


def main():
    N = int(eval(input()))
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N)]  # cum sum
    X[0] = A[0]
    for i in range(1, N):
        X[i] = X[i - 1] + A[i]
    # split to 2 parts (X_0, ..., X_(i-1)), (X_i, ..., X_(N-1))
    min_d = 10**10
    for i in range(2, N - 1):
        p, q = min_diff(X[:i])
        r, s = min_diff(X[i:], base=X[i - 1])
        d = max([p, q, r, s]) - min([p, q, r, s])
        min_d = min([min_d, d])
    print(min_d)


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    N = int(eval(input()))
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N + 1)]  # cum sum
    for i in range(N):
        X[i + 1] = X[i] + A[i]
    # split to 2 parts (X_0, ..., X_i), (X_(i+1), ..., X_N)
    ans = 10**10
    left = 0
    right = 2
    for i in range(1, N):
        while left < i:
            d = abs(X[left] - (X[i] - X[left]))
            d_next = abs(X[left + 1] - (X[i] - X[left + 1]))
            if d_next > d:
                break
            left += 1
        while right < N:
            d = abs((X[N] - X[right]) - (X[right] - X[i]))
            d_next = abs((X[N] - X[right + 1]) - (X[right + 1] - X[i]))
            if d_next > d:
                break
            right += 1
        p, q, r, s = X[left], X[i] - X[left], X[right] - X[i], X[N] - X[right]
        ans = min([ans, max([p, q, r, s]) - min([p, q, r, s])])
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
a=[sum(a[:i])+a[i] for i in range(len(a))]
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)

# 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
INF = 2 * 10**5 * 10**9
n = int(eval(input()))
a = list(map(int,input().split()))
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 2
p2 = 3
def update():
    global ans
    if p1 < p and p2 < n:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
    if p2 < n and p1 - 1 >= 1:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) )
    if p1 < p and p2-1 >= p:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) )
    if p1-1 >= 1 and p2-1 >= p:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) ) 
while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
    p2 += 1
update()
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and s[p1] < s[p] - s[p1]:
        p1 += 1
    while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
        p2 += 1
    update()
print(ans)

# Optimized solution
INF = 2 * 10**5 * 10**9
n = int(eval(input()))
a = list(map(int,input().split()))
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 1
p2 = 3
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and abs(s[p1] - s[p] + s[p1]) > abs(s[p1+1] - s[p] + s[p1 + 1]):
        p1 += 1
    while p2 < n and abs(s[p2] - s[p]  - s[n] + s[p2]) > abs(s[p2+1] - s[p]  - s[n] + s[p2+1]):
        p2 += 1
    ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))

b = a[0]
c = a[1]
d = a[2]
e = sum(a[3:n])
p = 0
q = 1
r = 2
while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
m = max(b,c,d,e) - min(b,c,d,e)

while q <= n-4:
  q += 1
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs((b+a[p+1])-(c-a[p+1])) <= abs(b-c):
    b += a[p+1]
    c -= a[p+1]
    p += 1
  while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) <= abs(d-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
print(m)
  

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

b,c,d,e = 0,a[0],a[1],sum(a[2:n])
p,q,r = -1,1,1
m = sum(a)

while q <= n-3:
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs(b-c+2*a[p+1]) <= abs(b-c):
    p += 1
    b += a[p]
    c -= a[p]
  while r+1 <= n-2 and abs(d-e+2*a[r+1]) <= abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
  q += 1
print(m)
# Original solution
import bisect
n = int(eval(input()))
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
cum.append(10**10)
mincost = 10 ** 10
for mid in range(2,n-1):
    ll = bisect.bisect_left(cum[:mid], cum[mid]//2)
    rl = bisect.bisect_left(cum[mid:], cum[mid+1] + (cum[n] - cum[mid+1])//2) + mid
    s = [0] * 4
    lw = abs(2*cum[ll] - cum[mid]) > abs(2*cum[ll-1] - cum[mid])
    rw = abs(2*cum[rl] - cum[mid] - cum[n]) > abs(2*cum[rl-1] - cum[mid] - cum[n])
    sums = [cum[ll - lw], cum[mid] - cum[ll - lw], cum[rl - rw] - cum[mid], cum[n] - cum[rl - rw]]
    mincost = min(mincost, max(sums) - min(sums))
print(mincost)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    lrsum += new
    l[mid] = l[mid-1]
    unk = a[l[mid]]
    while(abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk)):
        llsum += unk
        lrsum -= unk
        l[mid] += 1
        unk = a[l[mid]]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(list(range(2, n-2))):
    new = a[mid]
    rlsum += new
    r[mid] = r[mid+1]
    unk = a[r[mid] - 1]
    while(abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk)):
        rrsum += unk
        rlsum -= unk
        r[mid] -= 1
        unk = a[r[mid] - 1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k,h):
    j=spl_l(i,j)
    k=spl_r(i,k)
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=calc(j,1,k,h)
for i in range(2,N-2):
    ans=min(ans,calc(j,i,k,h))
print(ans)


# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=18**20
for i in range(1,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(ans)
# Original solution
n,m=list(map(int,input().split()))
List=[]
for i in range(m):
    road=list(map(int,input().split()))
    List.append(road)
    road=[road[1],road[0]]
    List.append(road)
ans=0
for i in range(1,n+1):
    for j in range(len(List)):
        if i==List[j][0]:
            ans+=1
    print(ans)
    ans=0


# Optimized solution
n,m=list(map(int,input().split()))
List=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    List.append([a,b])
    List.append([b,a])
ans=0
for i in range(1,n+1):
    for j in range(len(List)):
        if i==List[j][0]:
            ans+=1
    print(ans)
    ans=0