Snuke has an integer sequence A of length N.
He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.
Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

-----Constraints-----
 - 4 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

-----Sample Input-----
5
3 2 4 1 2

-----Sample Output-----
2

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
tmp=0
ca=[0]
for ai in a:
  tmp+=ai
  ca.append(tmp)
from bisect import bisect_right,bisect_left
ans=float('inf')

# 数列をまず半分に区切る。左i個と右n-i個 2<=i,n-i
f,g=1,3
for i in range(2,n-1):
  while abs(ca[i]-ca[f]-ca[f])>abs(ca[i]-ca[f+1]-ca[f+1]):
    f+=1
  while abs((ca[-1]-ca[g])-(ca[g]-ca[i]))>abs((ca[-1]-ca[g+1])-(ca[g+1]-ca[i])):
    g+=1
  l=(ca[f],ca[i]-ca[f],ca[-1]-ca[g],ca[g]-ca[i])
  ans=min(ans,max(l)-min(l))
  #print(l)
print(ans)


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

S = [0]

for a in A:
    S += [ S[-1] + a ]

l = 0
r = 2
ans = float('inf') 

for i in range(1, N-1):
    while S[i] - S[l+1] > S[l]:
        l += 1

    while S[N] - S[r+1] > S[r] - S[i]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]
  
    ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
B = list(accumulate(A))

l, c, r = 0, 1, 2
P = sum(A[:l])
Q = sum(A[l:c])
R = sum(A[c:r])
S = sum(A[r:])

ans = INF

for c in range(1, N-1):
	while True:
		if abs(P-Q) < abs((P+A[l])-(Q-A[l])):
			break
		if l == c-1:
			break
		P += A[l]
		Q -= A[l]
		l += 1

	while True:
		if abs(R-S) < abs((R+A[r])-(S-A[r])):
			break
		if r == N-1:
			break
		R += A[r]
		S -= A[r]
		r += 1

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

	Q += A[c]
	R -= A[c]

print(ans)


def tmp(a, b, c):
    return abs(a - b), abs(a - b + 2 * c)


def solve(string):
    n, *a = list(map(int, string.split()))
    l, c, r = 1, 2, 3
    sll, slr, srl, srr = sum(a[:l]), sum(a[l:c]), sum(a[c:r]), sum(a[r:])
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:

        d, dn = tmp(sll, slr, a[l])
        while dn < d:
            sll, slr, l = sll + a[l], slr - a[l], l + 1
            d, dn = tmp(sll, slr, a[l])
        d, dn = tmp(srl, srr, a[r])
        while dn < d:
            srl, srr, r = srl + a[r], srr - a[r], r + 1
            d, dn = tmp(srl, srr, a[r])
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        slr, srl, c = slr + a[c], srl - a[c], c + 1
    return str(ans)


def __starting_point():
    print((solve('\n'.join([input(), input()]))))

__starting_point()

import bisect

n=int(input())
arr=list(map(int,input().split()))
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=10**18
for i in range(2,n-1):
  suma=acum[i]
  sumb=acum[n]-suma
  posa=bisect.bisect_right(acum,suma//2)
  diffa=10**18
  if posa>=2:
    mina=min(acum[posa-1],acum[i]-acum[posa-1])
    maxa=max(acum[posa-1],acum[i]-acum[posa-1])
    diffa=maxa-mina
  if posa!=i:
    tmina=min(acum[posa],acum[i]-acum[posa])
    tmaxa=max(acum[posa],acum[i]-acum[posa])
    tdiffa=tmaxa-tmina
    if tdiffa<diffa:
      diffa=tdiffa
      mina=tmina
      maxa=tmaxa
  posb=bisect.bisect_right(acum,suma+sumb//2)
  diffb=10**18
  if posb>=i+2:
    minb=min(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    maxb=max(acum[posb-1]-acum[i],acum[n]-acum[posb-1])
    diffb=maxb-minb
  if posa!=n+1:
    tminb=min(acum[posb]-acum[i],acum[n]-acum[posb])
    tmaxb=max(acum[posb]-acum[i],acum[n]-acum[posb])
    tdiffb=tmaxb-tminb
    if tdiffb<diffb:
      diffb=tdiffb
      minb=tminb
      maxb=tmaxb
  ans=min(ans,max(maxa,maxb)-min(mina,minb))
print(ans)

def absdiff(a, b):
    return abs(b - a)


def solve(s):
    n, *a = list(map(int, s.split()))
    l, r, ans = 1, 3, sum(a)
    sll, slr, srl, srr = a[0], 0, sum(a[1:3]), sum(a[3:])
    for c in range(1, n - 1):
        slr += a[c]
        srl -= a[c]
        r = max(c, r)
        while l < c and absdiff(sll + a[l], slr - a[l]) < absdiff(sll, slr):
            sll, slr, l = sll + a[l], slr - a[l], l + 1
        while r < len(a) and absdiff(srl + a[r], srr - a[r]) < absdiff(srl, srr):
            srl, srr, r = srl + a[r], srr - a[r], r + 1
        _max, _min = max(sll, slr, srl, srr), min(sll, slr, srl, srr)
        ans = min(ans, absdiff(_min, _max))
    return ans


print((solve('\n'.join([input(), input()]))))


N=int(input())
A=list(map(int,input().split()))
AA=[0]*(N)
AA[0]=A[0]
for i in range(1,N):
  AA[i]=AA[i-1]+A[i]
l=0
r=2
p=[]
for m in range(1,N-2):
  sl=AA[m]
  sr=AA[N-1]-sl
  while abs(sl-2*AA[l])>abs(sl-2*AA[l+1]):
    l+=1
  while abs(AA[N-1]+sl-2*AA[r])>abs(AA[N-1]+sl-2*AA[r+1]):
    r+=1
  P=AA[l]
  Q=sl-P
  R=AA[r]-sl
  S=sr-R
  ans=max(P,Q,R,S)-min(P,Q,R,S)
  p.append(ans)
print(min(p))

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

cumsum = [0] * n
for i in range(n):
  if i == 0:
    cumsum[0] = a[0]
  else:
    cumsum[i] = cumsum[i-1] + a[i]
    
l = 0
r = 2
ans = sum(a)
for i in range(1, n-1):
  while cumsum[i] - cumsum[l+1] > cumsum[l]:
    l += 1
  while cumsum[-1] - cumsum[r+1] > cumsum[r] - cumsum[i]:
    r += 1
  a = cumsum[l]
  b = cumsum[i] - cumsum[l]
  c = cumsum[r] - cumsum[i]
  d = cumsum[-1] - cumsum[r]
  
  ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

from itertools import accumulate
from bisect import *
n = int(input())
a = list(map(int, input().split()))

a = [0]+list(accumulate(a))
#print(a)
ans = 10**18
for i in range(2, n):
    b = []
    m = a[i]
    l = bisect_right(a, m/2)
    if abs(a[l]-m/2) <= abs(a[l-1]-m/2):
        b.append(a[l])
        b.append(m-a[l])
    else:
        b.append(a[l-1])
        b.append(m-a[l-1])
    r = bisect_left(a, (a[-1]+m)/2)
    if abs(a[r]-(a[-1]+m)/2) <= abs(a[r-1]-(a[-1]+m)/2):
        b.append(a[r]-m)
        b.append(a[-1]-a[r])
    else:
        b.append(a[r-1]-m)
        b.append(a[-1]-a[r-1])

    #print(b)
    ans = min(ans, max(b)-min(b))

print(ans)


from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))

ans = 10 ** 18


A = tuple(accumulate(A, initial=0))
i = 1
j = 3


for mid in range(2, N - 1):
    # 左側をできるだけ等分
    b = A[i] - A[0]
    c = A[mid] - A[i]
    while i + 1 < mid and abs(b - c) > abs(A[mid] + A[0] - 2 * A[i+1]):
        i += 1
        b = A[i] - A[0]
        c = A[mid] - A[i]
    # 右側をできるだけ等分
    j = max(j, mid + 1)
    d = A[j] - A[mid]
    e = A[N] - A[j]
    while j + 1 < N and abs(d - e) > abs(A[N] + A[mid] - 2 * A[j+1]):
        j += 1
        d = A[j] - A[mid]
        e = A[N] - A[j]

    res = max(b, c, d, e) - min(b, c, d, e)
    ans = min(ans, res)

print(ans)

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

import itertools

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

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


N=int(input())
A=[int(x) for x in input().split()]
P,Q,R,S=A[0],0,A[1]+A[2],sum(A[3:])
l,r=1,3
ans=float("inf")
for i in range(2,N-1):
  Q+=A[i-1]
  while l<i-1:
    if abs(P-Q)>abs(P+A[l]-(Q-A[l])):
      P+=A[l]
      Q-=A[l]
      l+=1
    else:
      break
  R-=A[i-1]
  if i==r:
    R+=A[r]
    S-=A[r]
    r+=1
  while r<N-1:
    if abs(R-S)>abs(R+A[r]-(S-A[r])):
      R+=A[r]
      S-=A[r]
      r+=1
    else:
      break
  ans=min(ans,(max(P,Q,R,S)-min(P,Q,R,S)))
print(ans)

n = int(input())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

i1 = 1
i3 = 3
ans = 10**14
for i2 in range(2, n - 1):
    while i1 + 1 < i2 and abs(a_cs[i1] * 2 - a_cs[i2]) > abs(a_cs[i1 + 1] * 2 -
                                                             a_cs[i2]):
        i1 += 1

    while i3 + 1 < n and abs(a_cs[-1] + a_cs[i2] - a_cs[i3] *
                             2) > abs(a_cs[-1] + a_cs[i2] - a_cs[i3 + 1] * 2):
        i3 += 1

    p = a_cs[i1]  # [0,i1)
    q = a_cs[i2] - a_cs[i1]  # [i1, i2)
    r = a_cs[i3] - a_cs[i2]  # [i2, i3)
    s = a_cs[n] - a_cs[i3]  # [i3, n)
    cand = max(p, q, r, s) - min(p, q, r, s)
    ans = min(ans, cand)

print(ans)


# import math
# N = int(input())
# A_list = [int(i) for i in input().split()]


# def divide_list(num_list):
#   left = 0
#   right = len(num_list)
#   minimum = 10**9

#   while True:
#     c = (left+right)//2
#     left_sum = sum(num_list[:c])
#     right_sum = sum(num_list[c:])
#     diff = abs(left_sum - right_sum)

#     if minimum > diff:
#       minimum = diff
#       minimum_left = left
#       minimum_right = right
    
#     if left_sum > right_sum:
#       right = c
#     elif left_sum < right_sum:
#       left = c
#     else:
#       return num_list[:c], num_list[c:]

#     if c==left or c==right:
#       c = (minimum_left+minimum_right)//2
#       return num_list[:c], num_list[c:]

# tmp1_list, tmp2_list = divide_list(A_list)
# print(tmp1_list, tmp2_list)
# tmp11_list, tmp12_list = divide_list(tmp1_list)
# tmp21_list, tmp22_list = divide_list(tmp2_list)
# print(tmp11_list, tmp12_list, tmp21_list, tmp22_list)

# ans_list = [sum(tmp11_list), sum(tmp12_list), sum(tmp21_list), sum(tmp22_list)]
# ans_list.sort()

# print(ans_list[-1] - ans_list[0])


#102_D
N = int(input())
A = list(map(int, 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-2*AS[L]) > abs(Sum_L-2*AS[L+1]):
        L += 1

    while abs(AS[N-1]-2*AS[R]+AS[Mid]) > abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R += 1
    P = AS[L]
    Q = AS[Mid]-AS[L]
    S = AS[R]-AS[Mid]
    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)


import numpy as np
N = int(input())
A = np.zeros(N+2, dtype=np.int64)
A[1:-1] = input().split()

np.cumsum(A, out = A)
total = A[-1]
A[-1] = 10 ** 18

left = np.searchsorted(A, A/2)
P1 = A[left-1]
P2 = A[left]
Q1,Q2 = A-P1, A-P2

np.maximum(P1,Q2,out = P1)
np.minimum(P2,Q1,out = P2)
P,Q = P1,P2

right = np.searchsorted(A,(total+A)/2)
R1 = A[right-1] - A
R2 = A[right] - A
S1 = total - A[right-1]
S2 = total - A[right]
np.maximum(R1,S2,out=R1)
np.minimum(R2,S1,out=R2)
R,S = R1,R2

PQRS = np.vstack([P,Q,R,S])
x = np.max(PQRS, axis=0) - np.min(PQRS, axis=0)
answer = (x[1:-1].min())
print(answer)

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

cum = [0]
for ai in a:
    cum.append(cum[-1] + ai)

ans = float('inf')

for i in range(2, n-1):
    bc = cum[i]
    de = cum[-1] - cum[i]
    bc_mid = bc / 2
    de_mid = (cum[i] + cum[-1]) / 2

    i_bc = bisect.bisect_left(cum, bc_mid)
    i_de = bisect.bisect_left(cum, de_mid)

    # print(i_bc)
    # print(i_de)

    for cum_b in (cum[i_bc-1], cum[i_bc]):
        for cum_d in (cum[i_de-1], cum[i_de]):
            b = cum_b
            c = bc - b
            d = cum_d - bc
            e = de - d
            bcde = [b, c, d, e]
            bcde.sort()
            ans = min(ans, bcde[-1]-bcde[0])

print(ans)

from itertools import accumulate


def solve(string):
    n, *a = list(map(int, string.split()))
    *a, = accumulate(a)
    l, c, r = 0, 1, 2
    sll, slr, srl, srr = a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r]
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:
        while abs(a[c] - 2 * a[l + 1]) < abs(a[c] - 2 * a[l]):
            l += 1
        while abs(a[-1] + a[c] - 2 * a[r + 1]) < abs(a[-1] + a[c] - 2 * a[r]):
            r += 1
        sll, slr, srl, srr = a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r]
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        c+=1
    return str(ans)


def __starting_point():
    print((solve('\n'.join([input(), input()]))))

__starting_point()

import itertools
n = int(input())
A = [int(i) for i in input().split()]
A_sum = [0]+list(itertools.accumulate(A))
"""累積和は単調増加
4パートに分ければいいので別ける箇所3点left,mid,rightを探す．
全探索はTLEなのでmidに関するループ探索を行うと，条件式からl,rは決まる．
今回の問題では差をなくすことが目的なので，0~l,l~iとi~r,r~nの差が小さい時がベスト
この条件のもと，lとrを決める．for文で書く場合break入れないとTLE

"""
ans = 10**9
P,Q,R,S = 0,0,0,0
l = 0
r = 2
for i in range(1,n):
    while(l<i and abs(A_sum[l]-(A_sum[i]-A_sum[l])) >= abs(A_sum[l+1]-(A_sum[i]-A_sum[l+1]))):
        #単調増加だから超えるような時はp,qの差が大きくなる時だよね
        l += 1
    while(r<n and abs((A_sum[n]-A_sum[r]) -(A_sum[r]-A_sum[i])) >= abs((A_sum[n]-A_sum[r+1])-(A_sum[r+1]-A_sum[i]))):
        r += 1
    P = A_sum[l]
    Q = A_sum[i]-P
    R = A_sum[r]-A_sum[i]
    S = A_sum[n]-A_sum[r]
    ans =min(ans,abs(max(P,Q,R,S)-min(P,Q,R,S)))
    

print(ans)

#!/usr/bin/env python3
from itertools import accumulate
from bisect import bisect
n = int(input())
a = list(map(int, input().split()))
ans = 10**9
cs = [0] + list(accumulate(a))
for i in range(2, n - 1):
    left = cs[i]
    right = cs[-1] - cs[i]
    lm = bisect(cs, left // 2)
    l1, l2 = cs[lm], left - cs[lm]
    l3, l4 = cs[lm - 1], left - cs[lm - 1]
    if abs(l1 - l2) > abs(l3 - l4):
        l1 = l3
        l2 = l4
    rm = bisect(cs, left + right // 2)
    r1, r2 = cs[rm] - cs[i], right - (cs[rm] - cs[i])
    r3, r4 = cs[rm - 1] - cs[i], right - (cs[rm - 1] - cs[i])
    if abs(r1 - r2) > abs(r3 - r4):
        r1 = r3
        r2 = r4
    ans = min(ans, max(l1, l2, r1, r2) - min(l1, l2, r1, r2))
print(ans)


N = int(input())
A = list(map(int,input().split()))
B = [0]
tmp = 0
for a in A:
    tmp += a
    B.append(tmp)

l = 1
r = 3
cut = []
for i in range(2,N-1):
    Lm = float("inf")
    Rm = float("inf")
    c = [0,i,0]
    for j in range(l,i):
        tmp = abs(B[i]-2*B[j])
        if tmp > Lm:
            c[0] = j-1
            l = j-1
            break
        Lm = tmp
    else:
        c[0] = i-1
        l = i-1
    for k in range(r,N):
        tmp = abs((B[N]-B[k])-(B[k]-B[i]))
        if tmp > Rm:
            c[2] = k-1
            r = k-1
            break
        Rm = tmp
    else:
        c[2] = N-1
        r = N
    cut.append(c)
#print(cut)
ans = float("inf")
for p,q,r in cut:
    P = B[p]
    Q = B[q]-B[p]
    R = B[r]-B[q]
    S = B[N]-B[r]
    ans = min(ans,max(P,Q,R,S)-min(P,Q,R,S))
print(ans)


N = int(input())

#累積和で受け取る
A = [0] * N
S = 0
for i, a in enumerate(input().split()):
    S += int(a)
    A[i] = S

answer = S

#indexは最後に回収する番号
B = 0
D = 0

for C in range(1, N - 2):
    D = max(D, C + 1)
    SB = A[B]
    SC = A[C] - A[B]
    SD = A[D] - A[C]
    SE = S - A[D]
    left_score = abs(SB - SC)
    #BCの境界の調整
    while True:
        B_ = B + 1
        SB_ = A[B_]
        SC_ = A[C] - SB_
        x = abs(SB_  - SC_)
        if left_score > x:
            B, SB, SC, left_score = B_, SB_, SC_, x
            continue
        break

    right_score = abs(SE - SD)
    while True:
        D_ = D + 1
        SD_ = A[D_] - A[C]
        SE_ = S - A[D_]
        x = abs(SD_ - SE_)
        if right_score > x:
            D, SD, SE, right_score = D_, SD_, SE_, x
            continue
        break

    score = max(SB, SC, SD, SE) - min(SB, SC, SD, SE)
    answer = min(score, answer)
print (answer)


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



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

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

l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)


#102_D
N=int(input())
A=list(map(int,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-2*AS[L])>abs(Sum_L-2*AS[L+1]):
        L+=1
    
    while R<=N-3 and abs(AS[N-1]-2*AS[R]+AS[Mid])>abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R+=1
    P=AS[L]
    Q=AS[Mid]-AS[L]
    S=AS[R]-AS[Mid]
    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)

from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
p=0
q=2
for j in range(1,N-2):
    q=max(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        q+=1

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

print(ans)

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

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

ans=float("inf")
l=0
r=1
for i in range(1, n-2):
    while abs(ac[i]-2*ac[l+1]) < abs(ac[i]-2*ac[l]) and l < i+1:
        l+=1
    while abs(ac[-1]-2*ac[r+1]+ac[i]) < abs(ac[-1]-2*ac[r]+ac[i]) and r < n-2:
        r+=1
    t=[ac[l], ac[i]-ac[l], ac[r]-ac[i], ac[-1]-ac[r]]
    ans=min(ans, max(t)-min(t))
print(ans)


n = int(input())

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

# 累積和を求める
for i in range(n-1):
        a[i+1] += a[i]

#真ん中の仕切りを固定し、左右の配列についてさらに仕切りを動かして確認する
#累積和なので単調増加だから、左右の二つの配列について、仕切りを追加したときに差が最も小さい仕切りの位置を保存
l = 0
r = 2
ans = float("inf")
#mは真ん中の仕切りの位置
for m in range(1, n-1):
        #累積和が単調増加だから、mを固定したとき2a[l]-a[m]も単調増加で、lを増加させていくと徐々に減少しlとl+1で逆転する部分を左の仕切りとする。
        #2倍しないと累積和が単調増加のためずっと右辺が小さいままになる
        #部分配列の平均値に近い部分を二分探索で探すことも可能だが、平均計算処理と探索処理に加え、候補がbisectで求めた位置の前後も含まれるのでめんどくさい
        while abs(2*a[l] - a[m]) > abs(2*a[l+1] - a[m]): 
                l += 1
        while abs(2*a[r] - a[n-1] - a[m]) > abs(2*a[r+1] - a[n-1] - a[m]):
                r += 1

        bcde = [a[l], a[m]-a[l], a[r]-a[m],  a[n-1]-a[r]]
        ans = min(ans, max(bcde)-min(bcde))
print(ans)


N=int(input())
alist=list(map(int,input().split()))

slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)
#print(alist)
#print(slist)

dic_lp,dic_rp={},{}
lp,rp=0,2
for mp in range(1,N-2):
  #p1
  mindiff=slist[mp]
  while(lp<mp+1):
    sum1=slist[lp]
    sum2=slist[mp]-slist[lp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      lp+=1
      mindiff=diff
    else:
      lp-=1
      dic_lp[mp]=lp
      #print(mp,lp)
      break
    
  rp=max(rp,mp+1)
  mindiff=slist[-1]-slist[mp]
  while(rp<N):
    sum1=slist[-1]-slist[rp]
    sum2=slist[rp]-slist[mp]
    
    diff=abs(sum1-sum2)
    if mindiff>diff:
      rp+=1
      mindiff=diff
    else:
      rp-=1
      dic_rp[mp]=rp
      #print(mp,rp)
      break
    
min_diff=10**9
for mp in range(1,N-2):
  lp=dic_lp[mp]
  rp=dic_rp[mp]
  
  sum1=slist[lp]
  sum2=slist[mp]-slist[lp]
  sum3=slist[rp]-slist[mp]
  sum4=slist[-1]-slist[rp]
  #print(sum1,sum2,sum3,sum4)
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  #print(lp,mp,rp,diff)
  if diff<min_diff:
    min_diff=diff
    #print(min_diff)
  
print(min_diff)

import numpy as np

N = int(input())
A = np.zeros(N + 2, dtype = np.int64)
A[1:-1] = input().split()
np.cumsum(A, out = A)
total = A[-1]
A[-1] = 10 ** 18

left = np.searchsorted(A, A/2)
P1 = A[left - 1]
P2 = A[left]

Q1, Q2 = A - P1, A - P2

np.maximum(P1, Q2, out = P1)
np.minimum(P2, Q1, out = P2)
P, Q = P1, P2
right = np.searchsorted(A, (total + A)/2)
R1 = A[right - 1] - A
R2 = A[right] - A
S1 = total - A[right - 1]
S2 = total - A[right]
np.maximum(R1, S2, out = R1)
np.minimum(R2, S1, out = R2)
R, S = R1, R2

PQRS = np.vstack([P, Q, R, S])
x = np.max(PQRS, axis = 0) - np.min(PQRS, axis = 0)
answer = (x[1: -1].min())
print (answer)

import sys, os
from itertools import accumulate
import bisect

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

n = f()[0]
def get_mid(b, i):
    nonlocal n
    front_i_sum = b[i]

    idx1 = bisect.bisect_right(b, front_i_sum/2)
    if idx1 == 0:
        idx1 = 1
        max_fisrt = max(b[0], b[i]-b[0])
        min_first = min(b[0], b[i]-b[0])
    
    else:


        max1 = b[idx1]
        min1 = b[i] - b[idx1]

        max2 = b[i] - b[idx1-1]
        min2 = b[idx1-1]

        if max1 - min1 >= max2 - min2:
            max_fisrt = max2
            min_first = min2
        else:
            max_fisrt = max1
            min_first = min1


    idx2 = bisect.bisect_right(b, front_i_sum + (b[n-1] - b[i])/2)

    if idx2 == i+1:
        max_s = max(b[i+1]- b[i], b[n-1]- b[i+1])
        min_s = min(b[i+1]- b[i], b[n-1]- b[i+1])

    else:
        max1 = b[idx2] - front_i_sum
        min1 = b[n-1] - b[idx2]

        max2 = b[n-1] - b[idx2-1]
        min2 = b[idx2-1] - front_i_sum

        if max1 - min1 >= max2 - min2:
            max_s = max2
            min_s = min2
        else:
            max_s = max1
            min_s = min1
    
    return max(max_fisrt, max_s) - min(min_first, min_s)


def solve():
    a = f()
    b = list(accumulate(a))

    ans = int(2e14)
    for i in range(1, n-2):
        ans = min(ans, get_mid(b, i))

    print(ans)




solve()


import sys


def cumsum(li):
    ret = [0]
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


sys.setrecursionlimit(10000)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
# 最初が0
cs = cumsum(A)
assert len(cs) == N + 1


def calc_diff(d1, d2, d3):
    diffs = [
        cs[d1] - cs[0],
        cs[d2] - cs[d1],
        cs[d3] - cs[d2],
        cs[N] - cs[d3]
    ]
    return max(diffs) - min(diffs)


# 切る位置
# dn: n 番目の数列の開始インデックス
d0 = 0
d1 = 1
d2 = 2
d3 = 3
d4 = N
ans = INF
while d2 < d4 - 1:
    d012 = abs((cs[d1] - cs[d0]) - (cs[d2] - cs[d1]))
    while d1 < d2 - 1 and d012 > abs((cs[d1 + 1] - cs[d0]) - (cs[d2] - cs[d1 + 1])):
        d1 += 1
        d012 = abs((cs[d1] - cs[d0]) - (cs[d2] - cs[d1]))
    d234 = abs((cs[d3] - cs[d2]) - (cs[d4] - cs[d3]))
    while d3 < d4 - 1 and d234 > abs((cs[d3 + 1] - cs[d2]) - (cs[d4] - cs[d3 + 1])):
        d3 += 1
        d234 = abs((cs[d3] - cs[d2]) - (cs[d4] - cs[d3]))
    ans = min(ans, calc_diff(d1, d2, d3))
    d2 += 1

print(ans)


from itertools import accumulate
from bisect import bisect_left

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))


def score(i, j, k):
    mx = max(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    mn = min(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    return mx - mn


ans = float("inf")
i = 1
k = 3
for j in range(2, N - 1):
    while i < j - 1 and abs(S[j] - 2 * S[i]) > abs(S[j] - 2 * S[i+1]):
        i += 1
    while k <= j or k < N - 1 and abs(S[N] - 2 * S[k] + S[j]) > abs(S[N] - 2 * S[k+1] + S[j]):
        k += 1
    mx = max(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    mn = min(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    ans = min(ans, mx - mn)
print(ans)


# D - Equal Cut
import bisect

N = int(input())
A = list(int(a) for a in input().split())

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

ans = 10**18
for i in range(2, N-1):
    B = bisect.bisect_left(Acum, Acum[i]//2) - 1
    if abs(Acum[B] * 2 - Acum[i]) > abs(Acum[B+1] * 2 - Acum[i]):
        B += 1
    if B == i:
        B -= 1
    elif B == 0:
        B += 1
    P = Acum[B]
    Q = Acum[i] - Acum[B]
    D = bisect.bisect_left(Acum, Acum[i] + (Acum[-1]-Acum[i])//2) - 1
    if abs(Acum[D] * 2 - Acum[i] - Acum[-1]) > abs(Acum[D+1] * 2 - Acum[i] - Acum[-1]):
        D += 1
    if D == N:
        D -= 1
    elif D == i:
        D += 1
    R = Acum[D] - Acum[i]
    S = Acum[-1] - Acum[D]
    mi = min(P, Q, R, S)
    ma = max(P, Q, R, S)
    ans = min(ans, abs(ma - mi))
print(ans)

from statistics import mean

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

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

left_middle = 0
right_middle = 2

ans = float('inf')

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

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

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

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

print(ans)
        


from itertools import accumulate as ac
n=int(input())
s=list(ac(list(map(int,input().split()))))
c=0
d=2
f=s[-1]
k=f
for i in range(1,n-1):
    while s[i]>s[c]+s[c+1]:
        c+=1
    while s[i]+f>s[d]+s[d+1]:
        d+=1
    j=[s[c],s[i]-s[c],s[d]-s[i],f-s[d]]
    k=min(max(j)-min(j),k)
print(k)

from itertools import accumulate


def solve(string):
    n, *a = list(map(int, string.split()))
    *a, = accumulate(a)
    l, r, e = 0, 2, a[-1]
    ans = e
    for c in a[1:-2]:
        while a[l] + a[l + 1] < c:
            l += 1
        while a[r] + a[r + 1] < c + e:
            r += 1
        tmp = sorted([a[l], c - a[l], a[r] - c, e - a[r]])
        ans = min(ans, tmp[-1] - tmp[0])
    return str(ans)


def __starting_point():
    print((solve('\n'.join([input(), input()]))))

__starting_point()

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


n,*a=map(int,open(0).read().split())
for i in range(n-1):a[i+1]+=a[i]
j,k,m=0,2,1e18
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];m=min(m,max(t)-min(t))
print(m)

from bisect import bisect_right, bisect_left
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
A = [0] + A
a = list(accumulate(A))
answer = a[-1]

# 切り口はN-1個, 真ん中の選び方はN-3
for i in range(N - 3):
    left = a[i + 2]
    right = a[-1] - left
    p = bisect_left(a, left // 2)
    P1 = a[p]
    Q1 = left - P1
    P2 = a[p - 1]
    Q2 = left - P2
    if abs(P1 - Q1) <= abs(P2 - Q2):
        P = P1
        Q = Q1
    else:
        P = P2
        Q = Q2

    s = bisect_right(a, a[-1] - right // 2)
    S1 = a[-1] - a[s - 1]
    R1 = right - S1
    S2 = a[-1] - a[s]
    R2 = right - S2
    if abs(S1 - R1) <= abs(S2 - R2):
        S = S1
        R = R1
    else:
        S = S2
        R = R2

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

print(answer)

#!/usr/bin/env python3

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = list(map(int, input().split()))

ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s: abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k])
              for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s: abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a, b, c, d))
    if maxx - minn < res:
        res = maxx - minn

print(res)


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

from itertools import accumulate
from bisect import bisect_left

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

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)
print(ans)

N = int(input())
A = [0]*N
S = 0
for i,a in enumerate(input().split()):
  S += int(a)
  A[i] = S

answer = S

# index は最後に回収する番号で管理
B = 0
D = 2

for C in range(1,N-2):
  D = max(D,C+1)
  SB = A[B]
  SC = A[C] - A[B]
  SD = A[D] - A[C]
  SE = S - A[D]
  left_score = abs(SB - SC)
  # BCの境界の調整
  while True:
    B_ = B+1
    SB_ = A[B_]
    SC_ = A[C] - SB_
    x = abs(SB_ - SC_)
    if left_score > x:
      B,SB,SC,left_score = B_,SB_,SC_,x
      continue
    break
  right_score = abs(SD-SE)
  # DEの境界の調整
  while True:
    D_ = D+1
    SD_ = A[D_] - A[C]
    SE_ = S - A[D_]
    x = abs(SD_ - SE_)
    if right_score > x:
      D,SD,SE,right_score = D_,SD_,SE_,x
      continue
    break
  score = max(SB,SC,SD,SE) - min(SB,SC,SD,SE)
  answer = min(answer,score)
  
print(answer)


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

S = [0]
for i,a in enumerate(A,1):
    S.append(S[i-1]+a)
Sn = S[-1]
ans = Sn

i0 = 1
k0 = 3
for j in range(2,N-1):
    tmpS = S[j]
    for i in range(i0,j):
        if S[i] > tmpS/2:
            break
    i -= abs(tmpS - S[i] - S[i]) > abs(tmpS - S[i-1] - S[i-1])
    i0 = i
    for k in range(k0,N):
        if S[k]-tmpS > (Sn-tmpS)/2:
            break
    k -= abs(Sn-S[k] - S[k] + tmpS) > abs(Sn - S[k-1] - S[k-1] + tmpS)
    k0 = k
    P = (S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])
    ans = min(ans,max(P)-min(P))
print(ans)

n = int(input())
A = list(map(int, input().split()))

cumsum_A = []
cumsum = 0
for a in A:
    cumsum += a
    cumsum_A.append(cumsum)

ans = float('INF')
left = 0
right = 2

for center in range(1, n-2):
    ll_value = cumsum_A[left]
    lc_value = cumsum_A[center] - ll_value
    cr_value = cumsum_A[right] - cumsum_A[center]
    rr_value = cumsum_A[-1] - cumsum_A[right]

    while abs(ll_value - lc_value) > abs(ll_value - lc_value + 2*A[left+1]):
        if left == center - 1:
            break
        left += 1
        ll_value += A[left]
        lc_value -= A[left]

    while abs(cr_value - rr_value) > abs(cr_value - rr_value + 2 * A[right + 1]):
        if right == n - 2:
            break
        right += 1
        cr_value += A[right]
        rr_value -= A[right]

    candidate = max(ll_value, lc_value, cr_value, rr_value) - min(ll_value, lc_value, cr_value, rr_value)
    ans = min(ans, candidate)

print(ans)


from itertools import accumulate, islice
from bisect import bisect_left
 
n = int(input())
xs = [int(x) for x in input().split()]
 
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]
 
res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    minn, _, _, maxx = sorted((a,b,c,d))
    if maxx - minn < res:
        res = maxx - minn
 
print(res)

n=int(input())
A=[int(i) for i in input().split()]
AA=[A[0]]
for i in range(1,n):
  AA.append(AA[-1]+A[i])
tot=AA[-1]
import bisect
ans=float("inf")
for i in range(1,n-2):
  cur=AA[i]
  l=bisect.bisect_left(AA,cur//2)
  if l==0:
    L1=[0,float("inf")]
  else:
    L1=[AA[l-1],cur-AA[l-1]]
  L2=[AA[l],cur-AA[l]]
  
  r=bisect.bisect_left(AA,cur+(tot-cur)//2)
  if r-1==i:
    R1=[0,float("inf")]
  else:
    R1=[AA[r-1]-cur,tot-AA[r-1]]
  R2=[AA[r]-cur,tot-AA[r]]
  A11=L1+R1
  A12=L1+R2
  A21=L2+R1
  A22=L2+R2
  a11=max(A11)-min(A11)
  a12=max(A12)-min(A12)
  a21=max(A21)-min(A21)
  a22=max(A22)-min(A22)

  ans=min(ans,a11,a12,a21,a22)
print(ans)

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    S = [0] * len(A)
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s 
    l = 0
    b = 2
    m = S[-1]
    for c in range(1, N - 2):
        p, q = S[l], S[c] - S[l]
        while l + 1 < c:
            pn, qn = S[l + 1], S[c] - S[l + 1]
            if abs(pn - qn) >= abs(p - q):
                break
            p, q = pn, qn
            l += 1
        if b <= c:
            b = c + 1
        r, s = S[b] - S[c], S[-1] - S[b]
        while b + 1 < N - 1:
            rn, sn = S[b + 1] - S[c], S[-1] - S[b + 1]
            if abs(rn - sn) >= abs(r - s):
                break
            r, s = rn, sn
            b += 1
        m = min(m, max(p, q, r, s) - min(p, q, r, s))
    return m


print((main()))


import sys
from itertools import accumulate

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

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

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

    return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
bl=[0]
for i in a:bl.append(bl[-1]+i)
br=[0]
for i in a[::-1]:br.append(br[-1]+i)
def fl(r):
  suma=bl[r+1]
  ir=bisect_left(bl,suma//2)
  ans11,ans12=bl[ir],suma-bl[ir]
  ans21,ans22=bl[ir-1],suma-bl[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
def fr(l):
  r=(n-1)-l
  suma=br[r+1]
  ir=bisect_left(br,suma//2)
  ans11,ans12=br[ir],suma-br[ir]
  ans21,ans22=br[ir-1],suma-br[ir-1]
  if abs(ans11-ans12)<abs(ans21-ans22):return[ans11,ans12]
  else:return[ans21,ans22]
ans=10**20
for i in range(1,n-1):
  l=i
  r=i+1
  ll,lr=fl(i)
  rl,rr=fr(i+1)
  ans=min(ans,max(ll,lr,rl,rr)-min(ll,lr,rl,rr))
print(ans)

def main():
    from bisect import bisect_left

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

    # cumulative sum
    # cs[i] = sum(a[:i+1])
    cs = [0] * n
    for i in range(n):
        cs[i] = cs[i-1] + a[i]

    # search all possible indexes of middle split
    ans = 10**15
    for middle in range(2, n-1):
        # first_half = a[:middle]
        first = bisect_left(cs, cs[middle-1]//2, lo=1, hi=middle)
        if abs((cs[middle-1] - cs[first-1]) - cs[first-1]) < abs((cs[middle-1] - cs[first]) - cs[first]):
            p = cs[first-1]
            q = cs[middle-1] - cs[first-1]
        else:
            p = cs[first]
            q = cs[middle-1] - cs[first]

        # latter_half = a[middle:]
        last = bisect_left(cs, (cs[-1] + cs[middle-1])//2, lo=middle+1, hi=n)
        if abs((cs[-1] - cs[last-1]) - (cs[last-1] - cs[middle-1])) < abs((cs[-1] - cs[last]) - (cs[last] - cs[middle-1])):
            r = cs[last-1] - cs[middle-1]
            s = cs[-1] - cs[last-1]
        else:
            r = cs[last] - cs[middle-1]
            s = cs[-1] - cs[last]
        
        diff = max(p, q, r, s) - min(p, q, r, s)
        if diff < ans:
            ans = diff
    
    print(ans)

main()

N=int(input())
A=list(map(int,input().split()))
tmp=0
lr=[0]
for a in A:
  tmp+=a
  lr.append(tmp)

ans=float('inf')

f,g=1,3
for i in range(2,N-1):
  while abs(lr[i]-lr[f]-lr[f])>abs(lr[i]-lr[f+1]-lr[f+1]):
    f+=1
  while abs((lr[-1]-lr[g])-(lr[g]-lr[i]))>abs((lr[-1]-lr[g+1])-(lr[g+1]-lr[i])):
    g+=1
  l=(lr[f],lr[i]-lr[f],lr[-1]-lr[g],lr[g]-lr[i])
  ans=min(ans,max(l)-min(l))

print(ans)

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))

X = list(accumulate(A))

# A[:m]をできるだけ均等に、A[:l + 1], A[l + 1:]に分けるようなlを探す
l = 0
L = [-1] * N
for m in range(2, N - 1):
    target = X[m - 1] / 2
    while (l + 1 <= m) and abs(target - X[l]) >= abs(target - X[l + 1]):
        l += 1
    L[m] = l

# A[m:]をできるだけ均等に、A[:r + 1], A[r + 1:]に分けるようなrを探す
r = N - 1
r_sum = 0
R = [-1] * N
for m in reversed(list(range(2, N - 1))):
    target = (X[-1] - X[m - 1]) / 2
    while (r - 1 >= m) and abs((target - r_sum)) >= abs((target - (r_sum + A[r]))):
        r_sum += A[r]
        r -= 1
    R[m] = r

ans = float('inf')
for m in range(2, N - 1):
    li, ri = L[m], R[m]
    B, C, D, E = X[li], X[m - 1] - X[li], X[ri] - X[m - 1], X[-1] - X[ri]
    ans = min(ans, max(B, C, D, E) - min(B, C, D, E))

print(ans)


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

left = []
now = a[0]
le = 1
s = a[0]
for i in range(1,n):
    s += a[i]
    while le < i and abs(2*now-s) > abs(2*now+2*a[le]-s):
        now += a[le]
        le += 1
    left.append([now,s-now])

right = []
now = a[-1]
ri = 2
s = a[-1]
for i in range(2,n+1):
    s += a[-i]
    
    while ri < i and abs(2*now-s) > abs(2*now+2*a[-ri]-s):
        now += a[-ri]
        ri += 1
    right.append([now,s-now])

ans = float("INF")
for i in range(n-3):
    a,b = left[i]
    c,d = right[n-4-i]
    ans = min(ans,max(a,b,c,d)-min(a,b,c,d))
print(ans)

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)


import sys
input = sys.stdin.readline


def main():
    n = int(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)


def __starting_point():
    main()

__starting_point()

import sys
from itertools import accumulate
from bisect import bisect_left as bi_l

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

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

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

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

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

    return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import bisect
from collections import deque
n=int(input())
A=list(map(int,input().split()))
S=[A[0]]
for i in range(n-1):
  S.append(S[-1]+A[i+1])
ans=10**15
A1=deque([A[0]])
A2=deque(A[1:n])
for i in range(2,n-1):
  A1.append(A[i-1])
  A2.popleft()
  if len(A1)==2:
    M1=max(A1)
    m1=min(A1)
  else:
    x=bisect.bisect_left(S,S[i-1]//2,lo=0,hi=i+1)
    M11=max(S[x-1],S[i-1]-S[x-1])
    m11=min(S[x-1],S[i-1]-S[x-1])
    M12=max(S[x],S[i-1]-S[x])
    m12=min(S[x],S[i-1]-S[x])
    M1=min(M11,M12)
    m1=max(m11,m12)
  if len(A2)==2:
    M2=max(A2)
    m2=min(A2)
  else:
    x=bisect.bisect_left(S,S[i-1]+(S[-1]-S[i-1])//2,lo=0,hi=n)
    M21=max(S[x-1]-S[i-1],S[-1]-S[x-1])
    m21=min(S[x-1]-S[i-1],S[-1]-S[x-1])
    M22=max(S[x]-S[i-1],S[-1]-S[x])
    m22=min(S[x]-S[i-1],S[-1]-S[x])
    M2=min(M21,M22)
    m2=max(m21,m22)
  a=max(M1,M2)-min(m1,m2)
  if a<ans:
    ans=a
print(ans)

from itertools import *
N = int(input())
A = list(accumulate(map(int,input().split())))
l = 0
r = 2
t = A[-1]
a = t

for m in A[1:-2]:
  while abs(t-2*A[r]+m)>abs(t-2*A[r+1]+m):
    r+=1
  while abs(m-2*A[l])>abs(m-2*A[l+1]):
    l+=1
  x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
  a = min(a,x[3]-x[0])

print(a)

n=int(input())
a=list(map(int,input().split()))
accuml=[0]*n
accumr=[0]*n
accuml[0]=a[0]
accumr[0]=a[n-1]
for i in range(n-1):
    accuml[i+1]+=a[i+1]+accuml[i]
    accumr[i+1]+=a[n-i-2]+accumr[i]
ll=0
rr=n-3
ans=10**18
for i in range(1,n-2):
    sl=accuml[i]
    sr=accumr[n-2-i]
    while abs(accuml[ll+1]-sl/2)<abs(accuml[ll]-sl/2):
        ll+=1
    while abs(accumr[rr-1]-sr/2)<abs(accumr[rr]-sr/2):
        rr-=1
    maxi=max(sl-accuml[ll],accuml[ll],sr-accumr[rr],accumr[rr])
    mini=min(sl-accuml[ll],accuml[ll],sr-accumr[rr],accumr[rr])
    ans=min(ans,maxi-mini)
print(ans)

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    l = 0
    r = 2
    fl = lambda i,l:abs(cumsum[i + 1] - 2*cumsum[l + 1])
    fr = lambda i,r:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[r + 1] - cumsum[i + 1]))

    for i in range(1,N - 2):
        while fl(i,l + 1) < fl(i,l):
            l += 1
        while fr(i,r + 1) < fr(i,r):
            r += 1
        a = cumsum[l + 1]
        b = cumsum[i + 1] - a
        c = cumsum[r + 1] - a - b
        d = cumsum[-1] - a - b - c
        ans = min(ans,max(a,b,c,d) - min(a,b,c,d))
    print(ans)
    
def __starting_point():
    main()
__starting_point()

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

n=int(input())
A=list(map(int,input().split()))
S=[0] #累積和
cnt=0
for i in range(n):
    cnt+=A[i]
    S.append(cnt)

ans=S[n]
d1=1 #しきり1(i個目の右で切る)
d3=2 #しきり3

for d2 in range(2,n-1): #しきり2を全探索
    L=S[d2]
    R=S[n]-S[d2]
    for i in range(d1,d2): #しきり1を右に動かす
        if S[i]>=L/2:
            break
    if abs(S[i]-L/2)>=abs(S[i-1]-L/2): #しきり1を更新
        d1=i-1
    else:
        d1=i
    for i in range(d3,n): #しきり3を右に動かす
        if S[i]-S[d2]>=R/2:
            break
    if abs(S[i]-S[d2]-R/2)>=abs(S[i-1]-S[d2]-R/2): #しきり3を更新
        d3=i-1
    else:
        d3=i
    s=[S[d1],S[d2]-S[d1],S[d3]-S[d2],S[n]-S[d3]] #4分割の結果
    ans=min(max(s)-min(s),ans) #解答の更新
    #print(d1,d2,d3,s)
print(ans)

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,x = [int(i) for i in readline().split()]
#h,w = [int(i) for i in readline().split()]
n = int(input())
a = [int(i) for i in readline().split()]

from itertools import accumulate
acc = list(accumulate([0]+a))

j = 1
k = 3
ans = 10**18
for i in range(2,n):
    c = acc[i]//2
    while j < i-1 and acc[j] < c:
        j += 1

    c = (acc[-1]-acc[i])//2
    while k < n-1 and acc[k]-acc[i] < c:
        k += 1

    for jj in range(2):
        for kk in range(2):
            l = (acc[j-jj],acc[i]-acc[j-jj], acc[-1]-acc[k-kk], acc[k-kk]-acc[i])
            res = max(l) - min(l)
            ans = min(ans, res)

    
print(ans)   
    
    
    
    






from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(map(int,input().split()))
a=list(acc(a))

ans=10**18
for j in range(1,N-2):
    x=a[j]/2
    p=bl(a,x)
    if p==j: p-=1
    elif p>0 and x-a[p-1]<a[p]-x: p-=1

    y=(a[j]+a[N-1])/2

    q=bl(a,y)
    if q==N-1: q-=1
    elif q>j+1 and y-a[q-1]<a[q]-y: q-=1

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

print(ans)

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

from itertools import accumulate

s = list(accumulate(a))
#s = [a[0]]
#for i in range(1, n):
#    s.append(a[i] + s[i-1])

l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)


#解説解法
#15:49
n = int(input())
a = list(map(int,input().split()))
b = [a[0]]
for i in range(1,n):
  b.append(b[-1] + a[i])
c = []
for i in range(n):
  c.append([abs(b[i] - b[-1]/2),i])
h = -1
j = min(c,key= lambda x:x[0])[1]
p = 0
q = 0
r = b[j]
s = b[-1] - r
#print(p,q,r,s)
can = []
for i in range(n-2):
  q += a[i]
  while True:
    pnew = p + a[h+1]
    qnew = q - a[h+1]
    if abs(pnew-qnew) < abs(p-q):
      h += 1
      p = pnew
      q = qnew
    else:
      break
  r -= a[i]
  while True:
    rnew = r + a[j+1]
    snew = s - a[j+1]
    if abs(rnew-snew) < abs(r-s):
      j += 1
      r = rnew
      s = snew
    else:
      break
  if 1 <= i < n-2:
    can.append(max(p,q,r,s) - min(p,q,r,s))
    #print(p,q,r,s)
#print(can)
print(min(can))

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

N = int(input())
A = list(map(int, input().split()))
s = 0
S = [0]*N
for i, a in enumerate(A):
    s += a
    S[i] = s

t = S[-1]
ans = 10**20
j = 0
k = 2
for i in range(1,N-2):
    s = S[i]
    while abs(s-2*S[j+1]  ) < abs(s-2*S[j]  ): j+=1
    while abs(t-2*S[k+1]+s) < abs(t-2*S[k]+s): k+=1
    
    v = (S[j], s-S[j], S[k]-s, t-S[k])
    ans = min(ans, max(v)-min(v))
    
    #print(i,j,k, v)
print(ans)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
S = [0]
for a in A:
    S += [S[-1] + a]

ans = float("inf")
l = 0
r = 2
for i in range(1, N - 1):
    while S[l] < S[i] - S[l + 1]:
        l += 1
    while S[r] - S[i] < S[N] - S[r + 1]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]

    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)

inf = float('inf')

N = int(input())
a = tuple(map(int, input().split()))

c_sum = [0]
t = 0
for aa in a:
    t += aa
    c_sum.append(t)

ans = inf
p, q = 0, 2  # c_sum上のindex
for cut in range(2, N - 2 + 1):
    # [0, cut)と[cut, N)に分ける
    # 各区間を二分割する
    # 分割位置は、要素の合計の差が最小になるように取る

    # c_sum上のカーソルpを動かす
    # 右区間に一つ以上の要素が含まれるように、pはcut-1まで取る
    # c_sum[p]: 二分割した左区間の和
    # c_sum[cut] - c_sum[p]: 二分割した右区間の和
    while p < cut - 1:
        if abs(c_sum[cut] - c_sum[p] * 2) >= abs(c_sum[cut] - c_sum[p + 1] * 2):
            p += 1
        else:
            break

    # c_sum上のカーソルqを動かす
    # 右区間に一つ以上の要素が含まれるように、qはN-1まで取る
    # c_sum[q]: 二分割した左区間の和
    # c_sum[N] - c_sum[q]: 二分割した右区間の和
    while q < N - 1:
        if abs(c_sum[N] - c_sum[q] - (c_sum[q] - c_sum[cut])) >= abs(
                c_sum[N] - c_sum[q + 1] - (c_sum[q + 1] - c_sum[cut])):
            q += 1
        else:
            break

    cands = [c_sum[cut] - c_sum[p], c_sum[p], c_sum[N] - c_sum[q], c_sum[q] - c_sum[cut]]
    # print(cands)
    ans = min(ans, max(cands) - min(cands))
print(ans)


n=int(input())
a=list(map(int,input().split()))
score=[a[0],0,a[1]+a[2],sum(a[3:])]
ans=10**18
i,k=1,3
for j in range(2,n-1):
  score[1]+=a[j-1]
  score[2]-=a[j-1]
  while abs(score[0]-score[1])>abs(score[0]+a[i]-score[1]+a[i]):
    score[0]+=a[i]
    score[1]-=a[i]
    i+=1
  while abs(score[2]-score[3])>abs(score[2]+a[k]-score[3]+a[k]):
    score[2]+=a[k]
    score[3]-=a[k]
    k+=1
  ans=min(ans,max(score)-min(score))
print(ans)

from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
c = list(accumulate(a))
ans = float("inf")
x, y = 0, 2
for i in range(1, n - 2):
    while c[x] < c[i] - c[x + 1]:
        x += 1
    y = max(y, i + 1)
    while c[y] - c[i] < c[-1] - c[y + 1]:
        y += 1
    ma = max(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    mi = min(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
    ans = min(ans, ma - mi)
print(ans)

#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):

    wa = list(itertools.accumulate(A))
    # print(wa)
    m = INF
    # しゃくとり法
    atama1, atama2 = 0, 2
    # 真ん中iを固定する
    for i in range(1, N-2):
        # 0からi-1までの分割位置を決める
        # 最も前後の数列の和が近くなるように

        # 前の虫
        s0, s1 = wa[atama1], wa[i]-wa[atama1]
        for j in range(atama1+1, i):
            t0, t1 = wa[j], wa[i]-wa[j]
            # print(s0, s1, t0, t1, atama1)
            if t0 >= t1:
                if abs(s1-s0) >= abs(t1-t0):
                    s0, s1 = t0, t1
                    atama1 += 1
                break
            s0, s1 = t0, t1
            atama1 += 1
        # print(s0, s1, t0, t1)

        # 後ろの虫
        s2, s3 = wa[atama2]-wa[i], wa[N-1]-wa[atama2]
        for j in range(atama2+1, N):
            t2, t3 = wa[j]-wa[i], wa[N-1]-wa[j]
            if t2 >= t3:
                if abs(s3-s2) >= abs(t3-t2):
                    s2, s3 = t2, t3
                    atama2 += 1
                break
            s2, s3 = t2, t3
            atama2 += 1

        s = [s0, s1, s2, s3]
        # print(s)
        s.sort()
        m = min(s[3]-s[0], m)

    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


def __starting_point():
    main()

__starting_point()

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


N = int(input())
As = list(map(int,input().split()))
sum_a = [0]
for i in range(N):
  sum_a.append(As[i]+sum_a[i])
ans = float('inf')
p,q = 0,2
for cut in range(2,N-1):
  while p < cut-1:
    if abs(sum_a[cut]-sum_a[p]*2) >= abs(sum_a[cut]-sum_a[p+1]*2):
      p += 1
    else:
      break
      
  while q < N-1:
    if abs(sum_a[N]-sum_a[q]-(sum_a[q]-sum_a[cut])) >= abs(sum_a[N]-sum_a[q+1]-(sum_a[q+1]-sum_a[cut])):
      q += 1
    else:
      break
      
  ls = [sum_a[N]-sum_a[q],sum_a[q]-sum_a[cut],sum_a[cut]-sum_a[p],sum_a[p]]
  ans = min(ans,max(ls)-min(ls))
print(ans)
  
  
  


from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = [0] + list(map(int, input().split()))


ans = float('inf')
A = list(accumulate(A))

for m in range(2, N - 1):
    Lx = A[m] // 2
    Li = bisect_left(A, Lx)
    if abs(Lx - A[Li]) > abs(Lx - A[Li - 1]):
        Li -= 1

    Rx = (A[-1] + A[m]) // 2
    Ri = bisect_left(A, Rx)
    if abs(Rx - A[Ri]) > abs(Rx - A[Ri - 1]):
        Ri -= 1

    P, Q, R, S = A[Li], A[m] - A[Li], A[Ri] - A[m], A[-1] - A[Ri]
    tmp_ans = max(P, Q, R, S) - min(P, Q, R, S)
    ans = min(ans, tmp_ans)


print(ans)


def main():
    N = int(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)


def __starting_point():
    main()
__starting_point()

from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


N=int(input())
a=list(acc(map(int,input().split())))

ans=a[-1]
p=0
q=2
for j in range(1,N-2):
    q=max(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        q+=1

    x=[ a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q] ]
    ans=min(ans, max(x)-min(x))

print(ans)

#!/usr/bin/env python
from itertools import accumulate as ac
N = int(input())
A = list(ac(list(map(int, input().split()))))
l, r, t = 0, 2, A[-1]
c = t

for m in A[1:-2]:
    while t+m > A[r]+A[r+1]:
        r += 1
    while m > A[l]+A[l+1]:
        l += 1
    x = sorted([A[l],m-A[l],A[r]-m,t-A[r]])
    c = min(c,x[-1]-x[0])
print(c)


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

S = [0]

for a in A:
    S += [ S[-1] + a ]

l = 0
r = 2
ans = float('inf') 

for i in range(1, N-1):
    while S[i] - S[l+1] > S[l]:
        l += 1

    while S[N] - S[r+1] > S[r] - S[i]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]
  
    ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)


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

cul_sum = [0 for _ in range(N+1)]
for i in range(N):
    cul_sum[i+1] = A[i] + cul_sum[i]

def diff_left(center, left):
    return abs(cul_sum[center+1] - 2 * cul_sum[left+1])

def diff_right(center, right):
    return abs(cul_sum[N]-2*cul_sum[right+1]+cul_sum[center+1])

L = [-1 for _ in range(N-1)]
R = [-1 for _ in range(N-1)]
# 真ん中の切り方が i と i+1 の間
l = 0
r = 2
ans = float('inf')
for i in range(1, N-2):
    while l < i and diff_left(i, l) > diff_left(i, l+1):
        l += 1
    if r <= i:
        r = i+1
    while r < N and diff_right(i, r) > diff_right(i, r+1):
        r += 1
    part_sum = [
        cul_sum[l+1],
        cul_sum[i+1] - cul_sum[l+1],
        cul_sum[r+1] - cul_sum[i+1],
        cul_sum[N] - cul_sum[r+1],
    ]
    ans = min(ans, max(part_sum)-min(part_sum))

print(ans)


def solve(string):
    n, *a = list(map(int, string.split()))
    l, c, r = 1, 2, 3
    sll, slr, srl, srr = sum(a[:l]), sum(a[l:c]), sum(a[c:r]), sum(a[r:])
    ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
    while c < n - 1:
        d = abs(sll - slr)
        dn = abs(sll + 2 * a[l] - slr)
        while dn < d:
            sll, slr = sll + a[l], slr - a[l]
            l += 1
            d = abs(sll - slr)
            dn = abs(sll + 2 * a[l] - slr)
        d = abs(srl - srr)
        dn = abs(srl + 2 * a[r] - srr)
        while dn < d:
            srl, srr = srl + a[r], srr - a[r]
            r += 1
            d = abs(srl - srr)
            dn = abs(srl + 2 * a[r] - srr)
        ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
        slr += a[c]
        srl -= a[c]
        c += 1
    return str(ans)


def __starting_point():
    print((solve('\n'.join([input(), input()]))))

__starting_point()

n,*a=map(int,open(0).read().split())
for i in range(n-1):
    a[i+1]+=a[i]
j,k=0,2
m=1e18
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]
    m=min(m,max(t)-min(t))
print(m)

import math

n = int(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):
    nonlocal li
    while abs(s[rr] - 2 * s[li]) > abs(s[rr] - 2 * s[li + 1]):
        li += 1
        
def fsr(rr):
    nonlocal 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)

from itertools import accumulate

nim = int(input())
array = list(accumulate([int(i) for i in input().split()]))
l, r = 0, 1
ans = float("inf")
for i in range(1, nim-2):
    while abs(array[i] - 2 * array[l+1]) < abs(array[i] - 2 * array[l]) and l < i - 1: l += 1
    while abs(array[-1] - 2 * array[r+1] + array[i]) < abs(array[-1] - 2 * array[r] + array[i]) and r < nim - 2: r += 1
    t = [array[l], array[i] - array[l], array[r] - array[i], array[-1] - array[r]]
    ans = min(ans, max(t) - min(t))
print(ans)

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

l = 1
m = 2
r = 3
a = sum(A[:l])
b = sum(A[l:m])
c = sum(A[m:r])
d = sum(A[r:])
ans = max(a, b, c, d) - min(a, b, c, d)
# 尺取法(3点動かす)
while m < N-1:
    # a,bの差が最小になるまで左を動かす
    while l < m-1 and abs(a - b) > abs(a+A[l] - (b-A[l])):
        a += A[l]
        b -= A[l]
        l += 1
    # c,dの差が最小になるまで右を動かす
    while r < N-1 and abs(c - d) > abs(c+A[r] - (d-A[r])):
        c += A[r]
        d -= A[r]
        r += 1
    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
    # 真ん中を動かす
    b += A[m]
    c -= A[m]
    m += 1
    # 真ん中が右に追いついたら、右も合わせて+1する
    if m == r:
        c += A[r]
        d -= A[r]
        r += 1
print(ans)


from itertools import accumulate


def solve(string):
    n, *a = list(map(int, string.split()))
    *a, = accumulate(a)
    l, r, e, ans = 0, 2, a[-1], a[-1]
    for c in a[1:-2]:
        while a[l] + a[l + 1] < c:
            l += 1
        while a[r] + a[r + 1] < c + e:
            r += 1
        t = sorted([a[l], c - a[l], a[r] - c, e - a[r]])
        ans = min(ans, t[-1] - t[0])
    return str(ans)


def __starting_point():
    print((solve('\n'.join([input(), input()]))))

__starting_point()

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

#102_D
N = int(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)


n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [0] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = a_list[i - 1] + temp_list[i - 1]
 
l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 1):
    gap_min = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
    while l < m:
        l += 1
        gap = abs((temp_list[m] - temp_list[l]) - (temp_list[l] - temp_list[0]))
        if gap < gap_min:
            gap_min = gap
        else:
            l -= 1
            break
    else:
        l -= 1
    
    gap_min = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
    while r < n:
        r += 1
        gap = abs((temp_list[n] - temp_list[r]) - (temp_list[r] - temp_list[m]))
        if gap < gap_min:
            gap_min = gap
        else:
            r -= 1
            break
    else:
        r -= 1
    
    num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
    ans_temp = num_list[3] - num_list[0]
    if ans_temp < ans:
        ans = ans_temp
print(ans)

N = int(input())
A = list(map(int,input().split()))
from itertools import accumulate
P = list(accumulate(A))
l,right = 0,2
diff = float('inf')
for c in range(1,N-1):
    p = P[l]
    q = P[c]-P[l]
    while True:
        if abs(p+2*A[l+1]-q)>=abs(p-q):
            break
        p = P[l+1]
        q = P[c]-P[l+1]
        l += 1
    r = P[right]-P[c]
    s = P[-1]-P[right]
    while True:
        if abs(r+2*A[right+1]-s)>=abs(r-s):
            break
        r = P[right+1]-P[c]
        s = P[-1]-P[right+1]
        right += 1
    diff = min(diff,max(p,q,r,s)-min(p,q,r,s))
print(diff)