Problem:
 Score : 600 points    Problem Statement 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 1 5
3 2 4 1 2      Sample Output 1 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 .       Sample Input 2 10
10 71 84 33 6 47 23 25 52 64      Sample Output 2 36       Sample Input 3 7
1 2 3 1000000000 4 5 6      Sample Output 3 999999994

Solution (Python):
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)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    n = int(readline())
    a = list(map(int, readline().split()))
    cum = list(accumulate(a))

    left_lim = 1
    right_lim = n - 2
    first = 0
    second = 1
    third = 2
    ans = INF

    for second in range(left_lim, right_lim + 1):
        if third == second:
            third += 1

        p = cum[first]
        q = cum[second] - cum[first]
        r = cum[third] - cum[second]
        s = cum[n - 1] - cum[third]

        while first < second:
            if abs(p - q) > abs((p + a[first + 1]) - (q - a[first + 1])):
                first += 1
                p += a[first]
                q -= a[first]
            else:
                break

        while third < n - 1:
            if abs(r - s) > abs((r + a[third + 1]) - (s - a[third + 1])):
                third += 1
                r += a[third]
                s -= a[third]
            else:
                break

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    N = int(input())
    A = list(map(int, input().split()))

    
    import itertools
    import math
    B = list(itertools.accumulate(A))

    def f(a, i):
        return abs(B[i]-B[a]-B[a])
    def g(b, i):
        return abs(B[-1]-B[b]- (B[b]- B[i]))
    answer = pow(10, 10)
    for i in range(1, N-2):
        left1 = 0
        right1 = i
        while left1 + 2 < right1:
            c1 = left1 + (right1 - left1)//3
            c2 = right1 - (right1 - left1)//3
            if f(c1, i) > f(c2, i):
                left1 = c1
            else:
                right1 = c2
        left2 = i
        right2 = N-1
        while left2 + 2 < right2:
            c3 = left2 + (right2 - left2)//3
            c4 = right2 - (right2 - left2)//3
            if g(c3, i) > g(c4, i):
                left2 = c3
            else:
                right2 = c4
        p = sorted([(f(j, i), j) for j in range(left1, right1+1)])[0][1]
        q = sorted([(g(j, i), j) for j in range(left2, right2+1)])[0][1]
        m = min(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        M = max(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        answer = min(answer, M-m)

    print(answer)

    
if __name__ == "__main__":
    main()

Solution (Python):






from collections import deque





n=int(input())
a=list(map(int,input().split()))
r=[0]*(n+1)
s=sum(a)
q=0
s=2
ans=10**9
for i in range(n):
    r[i+1]=r[i]+a[i]
for l in range(2,n-1):
    for i in range(q,l):
        if a[i]>r[l]-2*r[i]:
            q=i
            break
    for i in range(s,n):
        if a[i]>(r[-1]-r[l])-2*(r[i]-r[l]):
            s=i
            break
    M=max(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
    m=min(r[q],r[l]-r[q],r[-1]-r[l]-(r[-1]-r[s]),r[-1]-r[s])
   
    ans=min(ans,(M-m))
print(ans)

Solution (Python):
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)

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    s = sum(A)
    cums = [0]
    for v in A:
        cums.append(cums[-1] + v)

    ret = float('inf')
    i, j, k = 1, 2, 3
    while j < N - 1:
        lm = cums[j]
        while i < j - 1 and cums[i] < lm // 2:
            i += 1
        if i > 2 and abs(lm - 2 * cums[i]) > abs(lm - 2 * cums[i - 1]):
            i -= 1

        rm = cums[N] - cums[j]
        while k < N - 1 and cums[k] - cums[j] < rm // 2:
            k += 1
        if k > j + 1 and abs(rm - 2 * (cums[k] - cums[j])) > abs(rm - 2 * (cums[k - 1] - cums[j])):
            k -= 1

        a, b, c, d = cums[i], cums[j] - cums[i], cums[k] - cums[j], cums[N] - cums[k]
        tmp = max(a, b, c, d) - min(a, b, c, d)
        
        ret = min(ret, tmp)
        j += 1
    print(ret)
    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))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])

def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]
    
    l,r=0,i
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if f(c1,i)>f(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    
    l,r=i+1,n-1
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))

Solution (Python):

import sys
from itertools import accumulate

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

N = ir()
A = lr()
Acum = list(accumulate(A))
slice1 = 0; slice3 = 2
answer = 10 ** 15
for i in range(1, N-2):
    
    slice2 = i
    if slice3 <= slice2:
        slice3 = slice2 + 1
    p = Acum[slice1]; q = Acum[slice2] - p
    r = Acum[slice3] - Acum[slice2]; s = Acum[-1] - Acum[slice3]
    while slice1 < i-1:
        p2 = Acum[slice1+1]
        q2 = Acum[slice2] - p2
        if abs(p2-q2) < abs(p-q):
            slice1 += 1
            p = p2; q = q2
        else:
            break
    while slice3 < N-2:
        r2 = Acum[slice3+1] - Acum[slice2]
        s2 = Acum[-1] - Acum[slice3+1]
        if abs(r2-s2) < abs(r-s):
            slice3 += 1
            r = r2; s = s2
        else:
            break
    ma = max(p, q, r, s); mi = min(p, q, r, s)
    temp = ma - mi
    if temp < answer:
        answer = temp
    
print(answer)

Solution (Python):
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):
    
    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

    
    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)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    X = [0 for _ in range(N + 1)]  
    for i in range(N):
        X[i + 1] = X[i] + A[i]
    
    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()

Solution (Python):
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]))):
        
        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)

Solution (Python):
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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)
    
if __name__ == '__main__':
    main()

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

def equal_l(cumsum,i):
    f = lambda j:abs(cumsum[i + 1] - 2*cumsum[j])
    l = 1
    r = i + 1
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) - f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    
    return cumsum[i + 1] - cumsum[l],cumsum[l]

def equal_r(cumsum,i,N):
    f = lambda j:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[j] - cumsum[i + 1]))
    l = i + 2
    r = N
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) -  f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    
    return  cumsum[-1] - cumsum[l],cumsum[l] - cumsum[i + 1]

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    for i in range(1,N - 2):
        a,b = equal_l(cumsum,i)
        c,d = equal_r(cumsum,i,N)
        ret = max(a,b,c,d) - min(a,b,c,d)
        ans = min(ans,ret)
    print(ans)
    
if __name__ == '__main__':
    main()

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

a = [0]+list(accumulate(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])

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

print(ans)

Solution (Python):
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 
d3=2 

for d2 in range(2,n-1): 
    L=S[d2]
    R=S[n]-S[d2]
    for i in range(d1,d2): 
        if S[i]>=L/2:
            break
    if abs(S[i]-L/2)>=abs(S[i-1]-L/2): 
        d1=i-1
    else:
        d1=i
    for i in range(d3,n): 
        if S[i]-S[d2]>=R/2:
            break
    if abs(S[i]-S[d2]-R/2)>=abs(S[i-1]-S[d2]-R/2): 
        d3=i-1
    else:
        d3=i
    s=[S[d1],S[d2]-S[d1],S[d3]-S[d2],S[n]-S[d3]] 
    ans=min(max(s)-min(s),ans) 
    
print(ans)

Solution (Python):
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 
d3=2 

for d2 in range(2,n-1): 
    L=S[d2]
    R=S[n]-S[d2]
    for i in range(d1,d2): 
        if S[i]>=L/2:
            break
    if abs(S[i]-L/2)>=abs(S[i-1]-L/2): 
        d1=i-1
    else:
        d1=i
    for i in range(d3,n): 
        if S[i]-S[d2]>=R/2:
            break
    if abs(S[i]-S[d2]-R/2)>=abs(S[i-1]-S[d2]-R/2): 
        d3=i-1
    else:
        d3=i
    s=[S[d1],S[d2]-S[d1],S[d3]-S[d2],S[n]-S[d3]] 
    ans=min(max(s)-min(s),ans) 
    
print(ans)

Solution (Python):
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)

    
    

    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)

Solution (Python):
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)

Solution (Python):
N, *A = map(int, open(0).read().split())

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

ans = 10 ** 9 + 7
l = 0
r = 2
for m in range(1, N):
    
    while l < m:
        s1 = abs((d[m] - d[l]) - d[l])
        s2 = abs((d[m] - d[l + 1]) - d[l + 1])
        if s1 > s2:
            l += 1
        else:
            break

    
    while m <= r < N:
        s1 = abs((d[N] - d[r]) - (d[r] - d[m]))
        s2 = abs((d[N] - d[r + 1]) - (d[r + 1] - d[m]))
        if s1 > s2 or m == r:
            r += 1
        else:
            break

    m1 = min(d[l], d[m] - d[l], d[r] - d[m], d[N] - d[r])
    m2 = max(d[l], d[m] - d[l], d[r] - d[m], d[N] - d[r])
    ans = min(ans, m2 - m1)

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=ruiseki(a)
ans=float('inf')

kirekomi=[1,3]

for i in range(2,n-1):
    while 1:
        if abs(lst[kirekomi[0]]-(lst[i]-lst[kirekomi[0]]))>abs(lst[kirekomi[0]+1]-(lst[i]-lst[kirekomi[0]+1])):
            kirekomi[0]+=1
        else:
            break
    
    while 1:
        if abs((lst[n]-lst[kirekomi[1]])-(lst[kirekomi[1]]-lst[i]))>abs((lst[n]-lst[kirekomi[1]+1])-(lst[kirekomi[1]+1]-lst[i])):
            kirekomi[1]+=1
        else:
            break
    
    
    p=lst[kirekomi[0]]
    q=lst[i]-lst[kirekomi[0]]
    r=lst[kirekomi[1]]-lst[i]
    s=lst[n]-lst[kirekomi[1]]
    anslst=[p,q,r,s]
    ans=min(ans,max(anslst)-min(anslst))
    
print(ans)

Solution (Python):

from itertools import product
import sys
try:
    from typing import List
except ImportError:
    pass


def bsearch1(i: int, a: "List[int]"):
    lb = 0
    rb = len(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if a[m] > i:
            rb = m
        else:
            lb = m
    return lb


def bsearch2(i: int, a: "List[int]"):
    lb = 0
    rb = len(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if a[m] > i:
            lb = m
        else:
            rb = m
    return lb


def solve(N: int, A: "List[int]"):
    cumleft = [0] * (N + 1)
    for i in range(N):
        cumleft[i + 1] = cumleft[i] + A[i]

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

    mleft = [bsearch1(cumi // 2, cumleft) for cumi in cumleft]
    mright = [bsearch2(cumi // 2, cumright) for cumi in cumright]
    ans = cumright[0]
    for i in range(2, N + 1 - 2):
        j1s = {mleft[i] - 1, mleft[i], mleft[i] + 1} - {0, i}
        j2s = {mright[i] - 1, mright[i], mright[i] + 1} - {i, N}
        for j1, j2 in product(j1s, j2s):
            p = cumleft[j1]
            q = cumleft[i] - cumleft[j1]
            r = cumleft[j2] - cumleft[i]
            s = cumright[j2]
            ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)


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


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

def eqcut(start, end, prev):
    prev_diff = abs(2 * cumA[prev] - cumA[start - 1] - cumA[end])
    for i in range(prev + 1, end + 1):
        diff = abs(2 * cumA[i] - cumA[start - 1] - cumA[end])
        if diff > prev_diff: break
        prev_diff = diff
    return i - 1

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

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

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]

for i in range(1, N - 2):
    B[0] = eqcut(0, i, B[0])  
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1, B[1])
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

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

print(ans)

Solution (Python):

def eqcut(start, end):
    target = (cumA[start - 1] + cumA[end]) / 2  

    ok = start
    ng = end + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if cumA[mid] <= target:
            ok = mid
        else:
            ng = mid
    
    if ok == end:
        return ok
    else:
        diff1 = abs( (cumA[end] - cumA[ok]) - (cumA[ok] - cumA[start - 1]))
        diff2 = abs( (cumA[end] - cumA[ok + 1]) - (cumA[ok + 1] - cumA[start - 1]))
        if diff1 <= diff2:
            return ok
        else:
            return ok + 1
            

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

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

S = [0, 0, 0, 0]
B = [0, 0]
ans = cumA[N - 1]

for i in range(1, N - 2):
    B[0] = eqcut(0, i)  
    S[0] = cumA[B[0]]
    S[1] = cumA[i] - cumA[B[0]]

    B[1] = eqcut(i + 1, N - 1)
    S[2] = cumA[B[1]] - cumA[i]
    S[3] = cumA[N - 1] - cumA[B[1]]

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

print(ans)

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

def bs_left(mid,mp):
  sum1=sum2=abs(2*slist[mid]-slist[mp])
  sum3=abs(2*slist[mid+1]-slist[mp])
  if mid>0:
    sum1=abs(2*slist[mid-1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)



dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  
  l,r=0,mp-1
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      
      break
  
  
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      
      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]
  
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

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

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)



dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  
  l,r=0,mp-1
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      
      break
  
  
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      
      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]
  
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

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

def bs_left(mid,mp):
  sum2=abs(2*slist[mid]-slist[mp])
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*slist[mid-1]-slist[mp])
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*slist[mid+1]-slist[mp])

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    

def bs_right(mid,mp):
  sum2=abs(2*(slist[mid]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==0:
    sum1=sum2
  else:
    sum1=abs(2*(slist[mid-1]-slist[mp])-(slist[-1]-slist[mp]))
  if mid==mp:
    sum3=sum2
  else:
    sum3=abs(2*(slist[mid+1]-slist[mp])-(slist[-1]-slist[mp]))

  if sum2<=sum1 and sum2<=sum3:
    return 0
  elif sum1<sum2:
    return -1
  elif sum2>sum3:
    return 1    
  
slist=[]
asum=0
for a in alist:
  asum+=a
  slist.append(asum)



dic_lp,dic_rp={},{}
for mp in range(1,N-2):  
  
  l,r=0,mp
  while(l<=r):
    mid=(l+r)//2
    ret=bs_left(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_lp[mp]=mid
      
      break
  
  
  l,r=mp+1,N-2
  while(l<=r):
    mid=(l+r)//2
    ret=bs_right(mid,mp)
    if ret==1:
      l=mid+1
    elif ret==-1:
      r=mid-1
    else:
      dic_rp[mp]=mid
      
      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]
  
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  
  if diff<min_diff:
    min_diff=diff    
  
print(min_diff)

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

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



dic_lp,dic_rp={},{}
lp,rp=0,2
for mp in range(1,N-2):
  
  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
      
      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
      
      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]
  
  
  sum_list=[sum1,sum2,sum3,sum4]
  sum_list.sort()
  diff=sum_list[-1]-sum_list[0]
  
  if diff<min_diff:
    min_diff=diff
    
  
print(min_diff)