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().rstrip().split(" ")))

t = list(0 for i in range(n+1))
for i in range(1, n+1):
    t[i] = t[i-1] + a[i-1]

def sum_a(i, j):
    return t[j]-t[i]

min_dif = sum_a(0, n)

i = 0
k = 2
for j in range(2, n-1):
    u = sum_a(0, j) // 2
    while sum_a(0, i) < u:
        i = i + 1
    if abs(sum_a(0, i-1)-sum_a(i-1, j)) < abs(sum_a(0, i) - sum_a(i, j)): 
        i = i - 1
    p = sum_a(0, i)
    q = sum_a(i, j)

    u = sum_a(j, n) // 2
    while sum_a(j, k) < u:
        k = k + 1
    if abs(sum_a(j, k-1)-sum_a(k-1, n)) < abs(sum_a(j, k) - sum_a(k, n)): 
        k = k - 1
    r = sum_a(j, k)
    s = sum_a(k, n)

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

print(min_dif)

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

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

ans = 10**20
l = 0
r = 2
for c in range(1, n-2):
    r = max(r, c+1)

    while l+1 < c and abs(a[c]-2*a[l]) >= abs(a[c]-2*a[l+1]):
        l += 1
    while r+1 < n and abs(a[-1]-2*a[r]+a[c]) >= abs(a[-1]-2*a[r+1]+a[c]):
        r += 1

    x = [a[l], a[c]-a[l], a[r]-a[c], a[-1]-a[r]]
    x.sort()
    ans = min(ans, x[3]-x[0])

print(ans)

Solution (Python):

def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    '''
    an example of using this function
    At-Coder ABC 102 - D
    '''

    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    funcs = (lambda ary, l, r: ary[r] - ary[l],
             lambda left, right: abs(left - right),
             lambda val1, val2: True if val1 < val2 else False)
    griefs = []
    for i in range(2, n - 1):
        
        l_split, l_diff, p, q = two_pointers(cul_ary, 0, i, l_split, *funcs)

        
        r_split, r_diff, r, s = two_pointers(cul_ary, i, n, r_split, *funcs)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Solution (Python):

def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        
        l_split, l_diff, p, q = two_pointers(cul_ary,
                                             0,
                                             i,
                                             l_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        
        r_split, r_diff, r, s = two_pointers(cul_ary,
                                             i,
                                             n,
                                             r_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Solution (Python):

def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    '''
    an example of using this function
    At-Coder ABC 102 - D
    '''

    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        
        l_split, l_diff, p, q = two_pointers(cul_ary,
                                             0,
                                             i,
                                             l_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        
        r_split, r_diff, r, s = two_pointers(cul_ary,
                                             i,
                                             n,
                                             r_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Solution (Python):

from itertools import accumulate


def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a))

    l_split = 1
    r_split = 3
    griefs = []

    for i in range(2, n - 1):
        l_split, l_diff, p, q = two_pointers(
            cul_ary, 0, i, l_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 < val2 else False)

        r_split, r_diff, r, s = two_pointers(
            cul_ary, i, n, r_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 < val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
S = [0]
for i in range(N):
        S.append(S[i]+A[i])
a = 1
c = 3
ans = S[N]
for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1
        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1
        ans = min(ans,(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])))
print(ans)

Solution (Python):
from itertools import *
input()
s=list(accumulate(map(int,input().split())))
l,r,t=0,2,s[-1];a=t
for m in s[1:-2]:
    while abs(t-2*s[r]+m)>abs(t-2*s[r+1]+m):r+=1
    while abs(m-2*s[l])>abs(m-2*s[l+1]):l+=1
    x=sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    a=min(a,x[3]-x[0])
print(a)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
for i in range(1,n):
    a[i] += a[i-1]
l,r = 0,0
ans = float("inf")

for c in range(1,n-2):
    while l < c-1:
        if 2 * a[l+1] > a[c]:
            if a[l+1] + a[l] < a[c]:
                l += 1
            break
        l += 1
    while r < n-2:
        if 2 * (a[r+1]-a[c]) > a[n-1] - a[c]:
            if a[r+1] + a[r] < a[n-1] + a[c]:
                r += 1
            break
        r += 1
    pqrs = [a[l],a[c]-a[l],a[r]-a[c],a[n-1]-a[r]]
    if ans > max(pqrs)-min(pqrs):
        ans = max(pqrs)-min(pqrs)
        
print(ans)

Solution (Python):
MAX = 10 ** 10
def m():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1,n):
        a[i] += a[i-1]
    ans = MAX
    left_i = 0
    right_i = 2
    for mid in range(1,n-2):
        while left_i < mid and abs(a[left_i+1] - (a[mid]-a[left_i+1])) < abs(a[left_i] - (a[mid]-a[left_i])):
            left_i += 1

        if right_i <= mid:
            right_i = mid+1

        while right_i < n-1 and abs((a[right_i+1] - a[mid]) - (a[n-1] - a[right_i+1])) < abs((a[right_i] - a[mid]) - (a[n-1] - a[right_i])):
            right_i += 1
        p = a[left_i]
        q = a[mid] - a[left_i]
        r = a[right_i] - a[mid]
        s = a[n-1] - a[right_i]
        ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    return ans

print(m())

Solution (Python):
from bisect import bisect_right


def main():
    """
    4 <= N <= 2 * 10^5
    1 <= Ai <= 10^9
    """
    N = int(input())
    *A, = map(int, input().split())

    ans = f(N, A)
    

    print(ans)


def test_ans():
    NA_ans = [
        (5, [3, 2, 4, 1, 2], 2),
        (10, [10, 71, 84, 33, 6, 47, 23, 25, 52, 64], 36),
        (7, [1, 2, 3, 1000000000, 4, 5, 6], 999999994),
    ]

    for N, A, ans in NA_ans:
        assert TLE(N, A) == ans
        assert f(N, A) == ans


def f(N, A):
    ans = float("inf")
    S = A[::]
    for i in range(1, N):
        S[i] += S[i-1]

    for mid in range(2, N-1):
        
        x = S[mid-1] / 2
        left = bisect_right(S, x)
        if abs(S[left-1] - x) < abs(S[left] - x):
            left -= 1

        y = (S[-1] + S[mid-1]) / 2
        right = bisect_right(S, y)
        if abs(S[right-1] - y) < abs(S[right] - y):
            right -= 1

        p = S[left]
        q = S[mid-1] - S[left]
        r = S[right] - S[mid-1]
        s = S[-1] - S[right]
        sums = (p, q, r, s)
        ans = min(ans, max(sums) - min(sums))

    return ans


def TLE(N, A):
    ans = float("inf")
    for b in range(1, N-2):
        for c in range(b+1, N-1):
            for d in range(c+1, N):
                B = A[:b]
                C = A[b:c]
                D = A[c:d]
                E = A[d:]
                print(B, C, D, E)

                *sums, = map(sum, [B, C, D, E])
                x = abs(max(sums) - min(sums))
                ans = min(ans, x)

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
input()
a=[int(i) for i in input().split()]
b=list(accumulate(a))
lp=0
rp=2
ans=float("INF")
for i in range(1,len(a)-2):
    while True:
        p=b[lp]
        q=b[i]-b[lp]
        r=b[rp]-b[i]
        s=b[len(a)-1]-b[rp]
        if abs(p-q)>abs(b[lp+1]-(b[i]-b[lp+1])) and lp+1!=i:
            lp+=1
        elif abs(r-s)>abs(b[rp+1]-b[i]-(b[len(a)-1]-b[rp+1])) and rp!=len(a)-1:
            rp+=1
        else:
            break
    ans=min(ans,abs(max(p,q,r,s)-min(p,q,r,s)))
print(ans)

Solution (Python):
from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
b = list(accumulate(a))
ll, rr = 0, 2
ans = float("INF")

for i in range(1, n-2):
  while True:
    p = b[ll]
    q = b[i]-b[ll]
    r = b[rr]-b[i]
    s = b[n-1]-b[rr]
    lt = abs(p-q)
    rt = abs(r-s)
    if abs(b[ll+1]-(b[i]-b[ll+1]))<lt:
      ll+=1
    elif abs((b[rr+1]-b[i])-(b[n-1]-b[rr+1]))<rt:
      rr+=1
    else:
      break
  ans = min(ans, abs(max(p, q, r, s)-min(p, q, r, s)))
print(ans)

Solution (Python):

def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    
    from operator import add, lt
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    ary_func = lambda ary, l, r: ary[r] - ary[l]
    comb_func = lambda left, right: abs(left - right)
    comp_func = lt
    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        
        l_split, l_diff, p, q = two_pointers(cul_ary, 0, i, l_split, ary_func,
                                             comb_func, comp_func)
        
        r_split, r_diff, r, s = two_pointers(cul_ary, i, n, r_split, ary_func,
                                             comb_func, comp_func)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))

Solution (Python):

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



















cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)
    diff = abs(left_sum - right_sum)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(tmp_left_sum - tmp_right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum

    else:
        return r - 1, tmp_diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    
    l_split, l_diff, p, q = two_pointers(0, i, l_split)
    
    r_split, r_diff, r, s = two_pointers(i, n, r_split)

    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    ans = sys.maxsize

    S = [0] * (N+1)
    for i in range(0, N):
        S[i+1] = A[i] + S[i]
    
    lj = 1
    left_diffs = {}
    for i in range(2, N-1):
        left_diff = (sys.maxsize, 0, 0)
        for j in range(lj, i):
            a = S[j]-S[0]
            b = S[i]-S[j]
            
            if left_diff[0] > abs(a-b):
                left_diff = (abs(a-b), a, b)
            else:
                break
        lj = j-1 if j-1 > 0 else 1
        left_diffs[i] = left_diff

    right_diffs = {}
    rj = N-1
    for i in range(N-1-1, 2-1, -1):
        right_diff = (sys.maxsize, 0, 0)
        
        for j in range(rj, i, -1):
            c = S[j]-S[i]
            d = S[-1]-S[j]
            
            if right_diff[0] > abs(c-d):
                right_diff = (abs(c-d), c, d)    
            else:
                break
        rj = j+1 if j+1 < N else N-1
        right_diffs[i] = right_diff
    
    for i in range(2, N-1): 
        _, a, b = left_diffs[i]
        _, c, d = right_diffs[i]
        
        ans = min(ans, (max(a, b, c, d) - min(a, b, c, d)))
    return ans
     

def main():
    N = read_int()
    A = read_int_n() 

    
    
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
*A, = map(int, input().split())
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]
INF = 10**30
ans = INF
def check(x, y, z):
    if 0 < y < x < z < N:
        B = (S[y], S[x]-S[y], S[z]-S[x], S[N]-S[z])
        return max(B)-min(B)
    return INF
y = z = 1
for x in range(2, N-1):
    s = S[x]
    while y < x and S[y+1]*2 <= s:
        y += 1
    t = S[N]-s
    while z < N and (S[z+1]-s)*2 <= t:
        z += 1
    for p in [0, 1]:
        for q in [0, 1]:
            ans = min(ans, check(x, y+p, z+q))
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
for i in range(1,n): a[i]+=a[i-1]
l,r,ans = 1,3,float("inf")
for i in range(2,n-1):
	num,num2 = abs(2*a[l-1]-a[i-1]),abs(2*a[r-1]-a[i-1]-a[n-1])
	while num>abs(2*a[l]-a[i-1]) and l<i-1: l,num = l+1,abs(2*a[l]-a[i-1])
	while num2>abs(2*a[r]-a[i-1]-a[-1]) and r<n-1: r,num2 = r+1,abs(2*a[r]-a[i-1]-a[-1])
	ans = min(ans,max(a[l-1],a[i-1]-a[l-1],a[r-1]-a[i-1],a[-1]-a[r-1])-min(a[l-1],a[i-1]-a[l-1],a[r-1]-a[i-1],a[-1]-a[r-1]))
print(ans)

Solution (Python):
from itertools import accumulate

def Sdiff(s, m, e):
    
    
    

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    
    N = int(input())
    l = list(map(int, input().split()))
    
    cl = list(accumulate(l))

    
    
    
    
    
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        
        
        c1 = partial(0, i, c1)
        
        c3 = partial(i+1, N-1, c3)

        
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        
        
        if diff < result:
            result = diff

    print(result)

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

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

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

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

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


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

    return (S,T,i)

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

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

    MIN+=[max([S_0,S_1,S_2,S_3])-min([S_0,S_1,S_2,S_3])]
    

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

print(min(MIN))

Solution (Python):







from itertools import accumulate

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

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


for mid in range(1,N-2):

	

	
	
	while l < mid and abs((SumA[mid] - SumA[l+1])-SumA[l+1]) < abs((SumA[mid] - SumA[l])-SumA[l]):
		l += 1

	
	
	while r < N-1 and abs((SumA[N-1]-SumA[r+1])-(SumA[r+1]-SumA[mid])) < abs((SumA[N-1] - SumA[r])-(SumA[r] - SumA[mid])):
		r += 1

	

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

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

print(ans)

Solution (Python):







from itertools import accumulate

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

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


for mid in range(1,N-2):

	

	
	
	while l < mid and abs(SumA[l+1]-(SumA[mid] - SumA[l+1])) < abs(SumA[l]-(SumA[mid] - SumA[l])):
		l += 1

	
	
	while r <= mid or (r < N and abs((SumA[r+1]-SumA[mid]) - (SumA[N-1]-SumA[r+1])) < abs((SumA[r] - SumA[mid]) - (SumA[N-1] - SumA[r]))):
		r += 1

	

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

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

print(ans)

Solution (Python):

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



















INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)
    diff = abs(left_sum - right_sum)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(tmp_left_sum - tmp_right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, tmp_diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))

Solution (Python):
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
def f(N,s):
    ans=s[-1]
    p=0
    q=2
    for i in range(2,N-1):
        while abs(s[i-1]-2*s[p])>abs(s[i-1]-2*s[p+1]):
            p+=1
        while abs(s[q]*2-s[i-1]-s[-1])>abs(s[q+1]*2-s[i-1]-s[-1]):
            q+=1
        t=[s[i-1]-s[p],s[p],s[q]-s[i-1],s[-1]-s[q]]
        ans=min(ans,max(t)-min(t))
    print(ans)
    return 
f(N,s)

Solution (Python):
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=s[-1]
p=0
q=2
for i in range(2,N-1):
    while abs(s[i-1]-2*s[p])>abs(s[i-1]-2*s[p+1]):
        p+=1
    while abs(s[q]*2-s[i-1]-s[-1])>abs(s[q+1]*2-s[i-1]-s[-1]):
        q+=1
    t=[s[i-1]-s[p],s[p],s[q]-s[i-1],s[-1]-s[q]]
    ans=min(ans,max(t)-min(t))
print(ans)

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

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

a = 1
c = 3
ans = S[N]

for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        ans = min(ans,(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])))

print(ans)

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

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

a = 1
c = 3
ans_tmp = []
for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

Solution (Python):
from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=10**9
p=0
q=2
for i in range(2,N-1):
    while p<i-1 and abs(s[i-1]-2*s[p+1])<abs(s[i-1]-2*s[p]):
        p+=1
    if q<i:
        q+=1
    while q<N and abs(s[i-1]-2*s[q+1]+s[-1])<abs(s[i-1]-2*s[q]+s[-1]):   
        q+=1
    t=[s[q]-s[i-1],s[-1]-s[q],s[p],s[i-1]-s[p]]
    w=max(t)-min(t)
    ans=min(ans,w) 
print(ans)

Solution (Python):
import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))

Solution (Python):

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



















cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    for i in range(split, r):
        tmp_diff = abs(cal_sum(l, i) - cal_sum(i, r))
        if diff >= tmp_diff:
            diff = tmp_diff
        else:
            return i - 1, diff
    else:
        return r - 1, diff


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    
    l_split, l_diff = two_pointers(0, i, l_split, 10**12)
    
    r_split, r_diff = two_pointers(i, n, r_split, 10**12)

    p, q, r, s = cal_sum(0, l_split), cal_sum(l_split,
                                              i), cal_sum(i, r_split), cal_sum(
                                                  r_split, n)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))


print(min(griefs))

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


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


s = [0, 0, 0, 0]
b0 = 0
b2 = 2
score = []
for b1 in range(1, n - 2):
    for i in range(b1 - b0 - 1):
        b0 = b0 + 1
        if (abs(acc[b1] - acc[b0] * 2) > abs(acc[b1] - acc[b0 - 1] * 2)):
            b0 = b0 - 1
            break
    s[0] = acc[b0]
    s[1] = acc[b1] - acc[b0]

    for i in range(n - b2 - 2):
        b2 = b2 + 1
        if (abs(acc[n - 1] - acc[b2] * 2 + acc[b1]) > abs(acc[n - 1] - acc[b2 - 1] * 2 + acc[b1])):
            b2 = b2 - 1
            break
    s[2] = acc[b2] - acc[b1]
    s[3] = acc[n - 1] - acc[b2]

    score.append(max(s) - min(s))

print(min(score))

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

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

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        if S[a_before] > S[b] - S[a_before]:
                a=a_before
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                if abs(S[b]-S[i-1]-S[i-1]) < abs(S[b]-S[i]-S[i]):
                                        a=i-1
                                        a_before = i-1
                                        break
                                else:
                                        a=i
                                        a_before = i
                                        break
                else:
                        a=b-1
                        a_before = b-1

        if S[c_before] - S[b] > S[N] - S[c_before]:
                c=c_before
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                if abs((S[N]-S[i-1]) - (S[i-1]-S[b])) < abs((S[N]-S[i]) - (S[i]-S[b])):
                                        c=i-1
                                        c_before = i-1
                                        break
                                else:
                                        c=i
                                        c_before = i
                                        break
                else:
                        c=N-1
                        c_before = N-1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))