Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect

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

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

print(Ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect

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

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

print(Ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

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

Ans = 10**15
D = [0,1]
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    # 2分探索で分割位置を求め、その次の要素を含める・含めないの2通り考慮する
    for d in D:
        a1 = A[ai-d]
        a2 = A[i-1]
        canA.append((a1,a2))
    for d in D:
        b1 = B[bi-d]
        b2 = B[-1]
        canB.append((b1,b2))
    # 考慮した組み合わせで最小のものを記録
    for a in canA:
        for b in canB:
            x1,x2,x3,x4 = a[0],a[1],b[0],b[1]
            Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect

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

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

print(Ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

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

Ans = 10**15
D = [0,1]
# 真ん中の分割位置を全探索
for i in range(2,N-1):
    # 前半と後半に分離
    A,B = S[:i],S[i:]
    sumA,sumB = S[i-1],S[N-1]-S[i-1]
    canA,canB = [],[]
    # 前半部分,後半部分をそれぞれできるだけ均等になるように分割
    ai = bisect_left(A,sumA/2)
    bi = bisect_left(B,sumB/2+A[-1])
    # 2分探索で分割位置を求め、その次の要素を含める・含めないの2通り考慮する
    for d in D:
        a1 = A[ai-d]
        a2 = A[i-1]
        canA.append((a1,a2))
    for d in D:
        b1 = B[bi-d]
        b2 = B[-1]
        canB.append((b1,b2))
    # 考慮した組み合わせで最小のものを記録
    for a in canA:
        for b in canB:
            x1,x2,x3,x4 = a[0],a[1],b[0],b[1]
            Ans = min(Ans,max(x1,x2-x1,x3-x2,x4-x3)-min(x1,x2-x1,x3-x2,x4-x3))

print(Ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect

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

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

print(Ans)