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

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

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)

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

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

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)




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)

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

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

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

Solution (Python):

import sys
import itertools
INF = float("inf")


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

    wa = list(itertools.accumulate(A))
    
    m = INF
    
    atama1, atama2 = 0, 2
    
    for i in range(1, N-2):
        
        

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

        
        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]
        
        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))  
    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 = [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)

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

Solution (Python):
def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    _accum = 0
    accum = []
    for a in A:
        _accum += a
        accum.append(_accum)
    
    upper = 0
    bottom = 2
    result = 10 ** 18
    for middle in range(1, N-2):
        while True:
            if upper == middle -1:
                break
            up = accum[upper]
            btm = accum[middle] - accum[upper]
            if abs(up - btm) > abs((up+A[upper+1])-(btm-A[upper+1])):
                upper += 1
            else:
                break
        while True:
            if bottom == N - 2:
                break
            up = accum[bottom] - accum[middle]
            btm = accum[N-1] - accum[bottom]
            if abs(up - btm) > abs((up + A[bottom+1]) - (btm-A[bottom+1])):
                bottom += 1
            else:
                break
        li = [accum[middle] - accum[upper], accum[bottom] - accum[middle], accum[upper], accum[N-1] - accum[bottom]]
        li = [abs(_) for _ in li]
        result = min(result, max(li)-min(li))
    print(result)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    return


def B():
    return


def C():
    return


def D():
    n = I()
    a = LI()
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    ans = float("inf")
    for m in range(3,n):
        lu = a[m-1]
        ru = a[n]-a[m-1]
        lm = bisect.bisect_left(a,lu//2)
        rm = bisect.bisect_left(a,ru//2+a[m-1])
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        rm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm += 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
    print(ans)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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

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

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ruiseki = [0]*(n+1)

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


def judge(begin,mid,end):
  if ruiseki[mid]-ruiseki[begin] < ruiseki[end]-ruiseki[mid]:
    return True
  else:
    return False

def solvediff(begin,mid,end):
  return abs( ruiseki[mid]-ruiseki[begin] - (ruiseki[end]-ruiseki[mid]) )

def solve_num1(begin,mid,end):
  return abs( ruiseki[mid]-ruiseki[begin] )

def solve_num2(begin,mid,end):
  return abs( ruiseki[end]-ruiseki[mid] )


ans = float("inf")
for i in range(2,n-1):
  
  
  ok = i
  ng = 0
  min_num = float("inf")
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if judge(0,mid,i):
      ng = mid
    else:
      ok = mid
    if min_num > solvediff(0,mid,i):
      min_num = solvediff(0,mid,i)
      num1 = solve_num1(0,mid,i)
      num2 = solve_num2(0,mid,i)
  
  
  ok = n
  ng = i
  min_num = float("inf")
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if judge(i,mid,n):
      ng = mid
    else:
      ok = mid
    if min_num > solvediff(i,mid,n):
      min_num = solvediff(i,mid,n)
      num3 = solve_num1(i,mid,n)
      num4 = solve_num2(i,mid,n)
      
  ans = min(ans, max(num1,num2,num3,num4) - min(num1,num2,num3,num4))
  
print(ans)

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

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

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

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

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

Solution (Python):
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)
    
    
    min_diff = min(min_diff, max(P,Q,R,S) - min(P,Q,R,S))
    
    

print(min_diff)

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

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

while c <= N-2:
	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

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

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

print(err)

Solution (Python):
n = int(input())

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

acc = []

s = 0
for c in l:
    s += c
    acc.append(s)



left = [-1]*(n-1)


L = 0
M = 1

for M in range(1,n-2):
    if M == 1:
        left[M] = 0
    else:
        
        pre_bar = left[M-1]
        pre_gap = abs(acc[pre_bar] - (acc[M]-acc[pre_bar]))
        next_bar = M-1
        for nxt_bar in range(pre_bar+1,M):
            nxt_gap = abs(acc[nxt_bar]-(acc[M]-acc[nxt_bar]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar - 1
                break
            else:
                pre_gap = nxt_gap
        left[M] = next_bar





right = [-1]*(n-1)


for M in range(1,n-2)[::-1]:
    if M == n-3:
        right[M] = n - 2
    else:
        
        pre_bar = right[M+1]
        pre_gap = abs(acc[n-1]-acc[pre_bar] - (acc[pre_bar] - acc[M]))
        next_bar = M+1
        for nxt_bar in range(M+1,pre_bar)[::-1]:
            nxt_gap = abs(acc[n-1]-acc[nxt_bar] - (acc[nxt_bar]-acc[M]))
            if nxt_gap > pre_gap:
                next_bar = nxt_bar + 1
                break
            else:
                pre_gap = nxt_gap
        right[M] = next_bar


res = acc[n-1] + 1
for M in range(1,n-2):
    L = left[M]
    R = right[M]
    a,b,c,d = acc[L],acc[M]-acc[L],acc[R]-acc[M],acc[n-1]-acc[R]
    gap = max(a,b,c,d)-min(a,b,c,d)
    res = min(res,gap)

print(res)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import *
n = int(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):
def equal_cut(N: int, A: list) -> int:
    Sa = [0] * (N + 1)  
    for i, a in enumerate(A):
        Sa[i + 1] = Sa[i] + a

    li, ri = 1, 3
    ans = float('inf')
    for mi in range(2, N - 1):
        
        
        
        if ri <= mi:
            ri = mi + 1

        
        for temp_li in range(li + 1, mi):
            P, Q = Sa[temp_li - 1], Sa[mi] - Sa[temp_li - 1]
            nP, nQ = Sa[temp_li], Sa[mi] - Sa[temp_li]

            if abs(nP - nQ) <= abs(P - Q):
                
                li = temp_li
            else:
                
                
                
                break

        
        for temp_ri in range(ri + 1, N):
            R, S = Sa[temp_ri - 1] - Sa[mi], Sa[N] - Sa[temp_ri - 1]
            nR, nS = Sa[temp_ri] - Sa[mi], Sa[N] - Sa[temp_ri]

            if abs(nR - nS) <= abs(R - S):
                ri = temp_ri
            else:
                break

        P = Sa[li]
        Q = Sa[mi] - Sa[li]
        R = Sa[ri] - Sa[mi]
        S = Sa[N] - Sa[ri]
        temp = max(P, Q, R, S) - min(P, Q, R, S)

        if temp < ans:
            ans = temp

    return ans


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = equal_cut(N, A)
    print(ans)

Solution (Python):


import sys 
from itertools import accumulate


def diff(p,q,r,s):
  return abs(max(p,q,r,s) - min(p,q,r,s))



N = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
sum = list(accumulate(An))


ans = sys.maxsize
li,ri = 1, 3
for i in range(2, N-1):
  while sum[li] < sum[i]-sum[li]:
    li += 1
  while sum[ri]-sum[i] < sum[N]-sum[ri]:
    ri += 1

  P1,Q1 = sum[li], sum[i]-sum[li]
  P2,Q2 = sum[li-1], sum[i]-sum[li-1]
  R1,S1 = sum[ri]-sum[i], sum[N]-sum[ri]
  R2,S2 = sum[ri-1]-sum[i], sum[N]-sum[ri-1]

  ans = min(ans, diff(P1,Q1,R1,S1), diff(P1,Q1,R2,S2), diff(P2,Q2,R1,S1), diff(P2,Q2,R2,S2))

print(ans)

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

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

B = [0 for i in range(N)]
B[1] = 0
left = 0
for i in range(2, N - 1):
  t = abs(cs[i] - cs[left] * 2) 
  for j in range(left + 1, i):
    if abs(cs[i] - cs[j] * 2) > t:
      left = j - 1
      break
    t = abs(cs[i] - cs[j] * 2)
  else:
    left = i - 1
  B[i] = left
E = [0 for i in range(N)]
E[N - 2] = N - 2
right = N - 2
for i in range(N - 3, 0, -1):
  t = abs(cs[N - 1] - cs[right] * 2 + cs[i]) 
  for j in range(right - 1, i, -1):
    if abs(cs[N - 1] - cs[j] * 2 + cs[i]) > t:
      right = j + 1
      break
    t = abs(cs[N - 1] - cs[j] * 2 + cs[i])
  else:
    right = i + 1
  E[i] = right

Ans = 10**15
for i in range(1, N - 2):
  b = cs[B[i]]
  c = cs[i] - cs[B[i]]
  d = cs[E[i]] - cs[i]
  e = cs[-1] - cs[E[i]]
  t = max(b, c, d, e) - min(b, c, d, e)
  if Ans > t:
    Ans = t
print(Ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
h=[0]
for a in A:
    h.append(a+h[-1])
h.pop(0)
def spl_l(i,b):
    while abs(h[i]-2*h[b])>abs(h[i]-2*h[b+1]):
        b+=1
    return b
def spl_r(i,b):
    while abs(h[-1]-2*h[b]+h[i])>abs(h[-1]-2*h[b+1]+h[i]):
        b+=1
    return b
def calc(j,i,k):
    pqrs=[h[j],h[i]-h[j],h[k]-h[i],h[-1]-h[k]]
    ans=max(pqrs)-min(pqrs)
    return ans

j=0
k=2
ans=18**20
for i in range(1,N-2):
    j=spl_l(i,j)
    k=spl_r(i,k)
    ans=min(ans,calc(j,i,k))
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
llsum = a[0]
lrsum = a[1]
l = [0] * n
l[2] = 1
for mid in range(3, n-1):
    new = a[mid-1]
    lrsum += new
    l[mid] = l[mid-1]
    unk = a[l[mid]]
    while(abs(lrsum - llsum) > abs(lrsum - llsum - 2 * unk)):
        llsum += unk
        lrsum -= unk
        l[mid] += 1
        unk = a[l[mid]]
rrsum = a[n-1]
rlsum = a[n-2]
r = [0] * n
r[n-2] = n-1
for mid in reversed(range(2, n-2)):
    new = a[mid]
    rlsum += new
    r[mid] = r[mid+1]
    unk = a[r[mid] - 1]
    while(abs(rlsum - rrsum) > abs(rlsum - rrsum - 2 * unk)):
        rrsum += unk
        rlsum -= unk
        r[mid] -= 1
        unk = a[r[mid] - 1]
minabs = 10 ** 20
for mid in range(2, n-1):
    c0 = cum[l[mid]]
    c1 = cum[mid]
    c2 = cum[r[mid]]
    sums = (c0, c1 - c0, c2 - c1, cum[n] - c2)
    minabs = min(minabs, max(sums) - min(sums))
print(minabs)

Solution (Python):
from itertools import accumulate
n=int(input())
A=list(map(int,input().split()))
S=list(accumulate(A))
left=0
right=2
ans=float('inf')
for i in range(1,n-2):
    while abs(S[left]-(S[i]-S[left]))>abs(S[left+1]-(S[i]-S[left+1])):
        left+=1
    while abs(S[right]-S[i]-(S[n-1]-S[right]))>abs(S[right+1]-S[i]-(S[n-1]-S[right+1])):
        right+=1
    minL,maxL=min(S[left],S[i]-S[left]),max(S[left],S[i]-S[left])
    minR,maxR=min(S[right]-S[i],S[n-1]-S[right]),max(S[right]-S[i],S[n-1]-S[right])
    ans=min(ans,max(maxL,maxR)-min(minL,minR))
print(ans)

Solution (Python):

import numpy as np


N = int(input())
A = list(map(int, input().split()))
C = np.cumsum(A).tolist()

LL = [np.inf] * N
LR = [np.inf] * N

l = 0

for m in range(N-1):
    if l < m:
        LL[m] = C[l]
        LR[m] = C[m] - C[l]
        while l < m:
            LL_tmp = C[l+1]
            LR_tmp = C[m] - C[l+1]
            if abs(LL[m] - LR[m]) >= abs(LL_tmp - LR_tmp):
                l    += 1
                LL[m] = C[l]
                LR[m] = C[m] - C[l]
            else:
                break

B = A[::-1]
D = np.cumsum(B).tolist()

RL = [np.inf] * N
RR = [np.inf] * N

r = 0

for m in range(N-1):
    if r < m:
        RR[m] = D[r]
        RL[m] = D[m] - D[r]
        while r < m:
            RR_tmp = D[r+1]
            RL_tmp = D[m] - D[r+1]
            if abs(RR[m] - RL[m]) >= abs(RR_tmp - RL_tmp):
                r    += 1
                RR[m] = D[r]
                RL[m] = D[m] - D[r]
            else:
                break

RR = RR[::-1]
RL = RL[::-1]

X = np.array([LL[:-1], LR[:-1], RL[1:], RR[1:]])[:, 1:-1]

print(int(np.min(np.abs(np.max(X, axis=0) - np.min(X, axis=0)))))

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

N = int(input())
P = list(accumulate(list(map(int, input().split()))))
l, r = 0, 2
ans = P[N - 1]
for i in range(1, N - 2):
    while l < i and abs(P[i] - 2 * P[l]) > abs(P[i] - 2 * P[l + 1]):
        l += 1
    while r < N - 1 and abs(P[N - 1] - 2 * P[r] + P[i]) > abs(P[N - 1] - 2 * P[r + 1] + P[i]):
        r += 1
    minn = min(abs(P[i] - P[l]), P[l], abs(P[N - 1] - P[r]), abs(P[r] - P[i]))
    maxn = max(abs(P[i] - P[l]), P[l], abs(P[N - 1] - P[r]), abs(P[r] - P[i]))
    ans = min(ans, maxn - minn)
print(ans)

Solution (Python):

import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
from itertools import accumulate
input = stdin.readline
N = int(input())
A = [0] + list(map(int, input().split()))
acc = list(accumulate(A))


lefti = 0
righti = 0
ans = 10**15
for i in range(2, N-1):
    while abs(acc[lefti]-(acc[i]-acc[lefti])) > abs(acc[lefti+1]-(acc[i]-acc[lefti+1])):
        lefti += 1
    while abs(acc[righti]-acc[i]-(acc[-1]-acc[righti])) > abs(acc[righti+1]-acc[i]-(acc[-1]-acc[righti+1])):
        righti += 1
    minbc, maxbc = min(acc[lefti], acc[i]-acc[lefti]
                       ), max(acc[lefti], acc[i]-acc[lefti])
    minde, maxde = min(acc[righti]-acc[i], acc[-1]-acc[righti]
                       ), max(acc[righti]-acc[i], acc[-1]-acc[righti])
    
    ans = min(ans, max(maxbc, maxde)-min(minbc, minde))
print(ans)

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

s = list(accumulate(a))
ans = float("inf")

j = 0
k = 2

for i in range(1, n-2):
    while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
        j += 1
    while abs(s[n-1] - 2*s[k] + s[i]) > abs(s[n-1] - 2*s[k+1] + s[i]):
        k += 1
    t = max(s[j], s[i]-s[j], s[k]-s[i], s[n-1]-s[k]) - min(s[j], s[i]-s[j], s[k]-s[i], s[n-1]-s[k])
    ans = min(ans, t)

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
A = list(accumulate(A))

ans = float('inf')

for mid in range(1, N):
    L_target, R_target = A[mid] // 2, (A[mid] + A[-1]) // 2
    L_index, R_index = bisect_left(A, L_target), bisect_left(A, R_target)
    if abs(A[L_index - 1] - L_target) < abs(A[L_index] - L_target):
        L_index -= 1
    if abs(A[R_index - 1] - R_target) < abs(A[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = A[L_index], A[mid]-A[L_index], A[R_index]-A[mid], A[-1]-A[R_index]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

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

b,c,d,e = 0,a[0],a[1],sum(a[2:n])
p,q,r = -1,1,1
m = sum(a)

while q <= n-3:
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs(b-c+2*a[p+1]) <= abs(b-c):
    p += 1
    b += a[p]
    c -= a[p]
  while r+1 <= n-2 and abs(d-e+2*a[r+1]) <= abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
  q += 1
print(m)

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

b = a[0]
c = a[1]
d = a[2]
e = sum(a[3:n])
p = 0
q = 1
r = 2
while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) < abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
m = max(b,c,d,e) - min(b,c,d,e)

while q <= n-4:
  q += 1
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs((b+a[p+1])-(c-a[p+1])) <= abs(b-c):
    b += a[p+1]
    c -= a[p+1]
    p += 1
  while r+1 <= n-2 and abs((d+a[r+1])-(e-a[r+1])) <= abs(d-e):
    d += a[r+1]
    e -= a[r+1]
    r += 1
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
print(m)