Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0

for r in range(2, N - 1):
    # 左のしゃくとり
    P, Q = P2, Q2 = -1, -1
    p = 0
    q = 1
    while True:
        P2, Q2 = P, Q
        P = SUM[q - 1]
        Q = SUM[r - 1] - SUM[q - 1]
        if P < Q and q < r:
            q += 1
        else:
            break
    left_min, left_max = min(P, Q), max(P, Q)
    if P2 != -1:
        if abs(Q - P) > abs(Q2 - P2):
            left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右のしゃくとり
    R, S = R2, S2 = -1, -1
    s = r + 1
    while True:
        R2, S2 = R, S
        R = SUM[s - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[s - 1]
        if R < S and s < N - 1:
            s += 1
        else:
            break
    right_min, right_max = min(R, S), max(R, S)
    if R2 != -1:
        if abs(R - S) > abs(R2 - S2):
            right_min, right_max = min(R2, S2), max(R2, S2)

    # print(p, q, r, s)
    # print(P, Q, R, S)
    # print(P2, Q2, R2, S2)
    # print("----------")

    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)


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

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0
p = 0
q = 1
r = N // 2
s = r + 1
for r in range(2, N - 1):
    # 左
    P1, Q1 = P2, Q2 = -1, -1
    low, high = 1, r - 1
    while low + 1 < high:
        mid = (low + high) // 2
        P = SUM[mid - 1]
        Q = SUM[r - 1] - SUM[mid - 1]
        if P < Q:
            low = mid
        else:
            high = mid
    P1, Q1 = SUM[low - 1], SUM[r - 1] - SUM[low - 1]
    P2, Q2 = SUM[high - 1], SUM[r - 1] - SUM[high - 1]
    left_min, left_max = min(P1, Q1), max(P1, Q1)
    if abs(Q1 - P1) > abs(Q2 - P2):
        left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右
    R1, S1 = R2, S2 = -1, -1
    low, high = r + 1, N - 1
    while low + 1 < high:
        mid = (low + high) // 2
        R = SUM[mid - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[mid - 1]
        if R < S:
            low = mid
        else:
            high = mid
    R1, S1 = SUM[low - 1] - SUM[r - 1], SUM[N - 1] - SUM[low - 1]
    R2, S2 = SUM[high - 1] - SUM[r - 1], SUM[N - 1] - SUM[high - 1]
    right_min, right_max = min(R1, S1), max(R1, S1)
    if abs(R1 - S1) > abs(R2 - S2):
        right_min, right_max = min(R2, S2), max(R2, S2)

    # print(P1, Q1, R1, S1, sum([P1, Q1, R1, S1]), sum(A))
    # print(P2, Q2, R2, S2, sum([P2, Q2, R2, S2]), sum(A))
    # print("--------")
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(x) for x in input().split()]

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0

for r in range(2, N - 1):
    # 左のしゃくとり
    P, Q = P2, Q2 = -1, -1
    p = 0
    q = 1
    while True:
        P2, Q2 = P, Q
        P = SUM[q - 1]
        Q = SUM[r - 1] - SUM[q - 1]
        if P < Q and q < r:
            q += 1
        else:
            break
    left_min, left_max = min(P, Q), max(P, Q)
    if P2 != -1:
        if abs(Q - P) > abs(Q2 - P2):
            left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右のしゃくとり
    R, S = R2, S2 = -1, -1
    s = r + 1
    while True:
        R2, S2 = R, S
        R = SUM[s - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[s - 1]
        if R < S and s < N - 1:
            s += 1
        else:
            break
    right_min, right_max = min(R, S), max(R, S)
    if R2 != -1:
        if abs(R - S) > abs(R2 - S2):
            right_min, right_max = min(R2, S2), max(R2, S2)

    # print(p, q, r, s)
    # print(P, Q, R, S)
    # print(P2, Q2, R2, S2)
    # print("----------")

    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)


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

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

left_min = right_min = ans = float('INF')
left_max = right_max = 0
p = 0
q = 1
r = N // 2
s = r + 1
for r in range(2, N - 1):
    # 左
    P1, Q1 = P2, Q2 = -1, -1
    low, high = 1, r - 1
    while low + 1 < high:
        mid = (low + high) // 2
        P = SUM[mid - 1]
        Q = SUM[r - 1] - SUM[mid - 1]
        if P < Q:
            low = mid
        else:
            high = mid
    P1, Q1 = SUM[low - 1], SUM[r - 1] - SUM[low - 1]
    P2, Q2 = SUM[high - 1], SUM[r - 1] - SUM[high - 1]
    left_min, left_max = min(P1, Q1), max(P1, Q1)
    if abs(Q1 - P1) > abs(Q2 - P2):
        left_min, left_max = min(P2, Q2), max(P2, Q2)

    # 右
    R1, S1 = R2, S2 = -1, -1
    low, high = r + 1, N - 1
    while low + 1 < high:
        mid = (low + high) // 2
        R = SUM[mid - 1] - SUM[r - 1]
        S = SUM[N - 1] - SUM[mid - 1]
        if R < S:
            low = mid
        else:
            high = mid
    R1, S1 = SUM[low - 1] - SUM[r - 1], SUM[N - 1] - SUM[low - 1]
    R2, S2 = SUM[high - 1] - SUM[r - 1], SUM[N - 1] - SUM[high - 1]
    right_min, right_max = min(R1, S1), max(R1, S1)
    if abs(R1 - S1) > abs(R2 - S2):
        right_min, right_max = min(R2, S2), max(R2, S2)

    # print(P1, Q1, R1, S1, sum([P1, Q1, R1, S1]), sum(A))
    # print(P2, Q2, R2, S2, sum([P2, Q2, R2, S2]), sum(A))
    # print("--------")
    ans = min(max(left_max, right_max) - min(left_min, right_min), ans)

print(ans)