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 = [int(i) for i in input().split(" ")]

pref = [0]

for i in range(1,n+1):
    pref.append(pref[i-1] + A[i-1])

lt = 1
rt = 3
ans = 10**18
for i in range(2,n):
    while lt+1<i and abs(pref[i] - pref[lt+1] - pref[lt+1]) < abs(pref[i] - pref[lt] - pref[lt]):
        lt+=1
    
    while rt>=i and rt<n and (abs(pref[n] - pref[rt+1] - pref[rt+1] + pref[i]) < abs(pref[n] - pref[rt] - pref[rt] + pref[i])):
        rt+=1
    
    ans = min(ans, abs(max(pref[lt], pref[i]-pref[lt], pref[rt]-pref[i], pref[n]-pref[rt]) - min(pref[lt], pref[i]-pref[lt], pref[rt]-pref[i], pref[n]-pref[rt])))

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
def f(a):
    l, r = a[:2]
    m = 1
    b = [(l,r)]
    for i in range(2, n-2):
        r += a[i]
        while m<i and abs(l-r)>abs(l-r+a[m]*2): 
            l, r = l+a[m], r-a[m]
            m += 1
        b.append((l,r))
    return b
print(min(max(p,q,r,s)-min(p,q,r,s)
        for ((p,q),(r,s)) in zip(f(a), f(a[::-1])[::-1])))

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(b[i]+c[-i-1])
    y = min(b[i]+c[-i-1])
    r = min(r, x-y)
print(r)

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

cumsum = list(accumulate(A))
cumsum.insert(0, 0)

ans = float('inf')
for m in range(2, N-1):
    
    Lmid = cumsum[m] / 2
    Lx = bisect_left(cumsum, Lmid)
    if abs(Lmid-cumsum[Lx]) > abs(Lmid-cumsum[Lx-1]):
        Lx -= 1

    
    Rmid = (cumsum[m] + cumsum[N]) / 2
    Rx = bisect_left(cumsum, Rmid)
    if abs(Rmid-cumsum[Rx]) > abs(Rmid-cumsum[Rx-1]):
        Rx -= 1

    P, Q, R, S = cumsum[Lx], cumsum[m]-cumsum[Lx], cumsum[Rx]-cumsum[m], cumsum[N]-cumsum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Solution (Python):
INF = 99999999999
N = int(input())
a = list(map(int, input().split()))
ss = [0] * (N + 1)
s = 0
for i, n in enumerate(a):
    s += n
    ss[i + 1] = s


def psum(l, r):
    return ss[r] - ss[l]

min_ns = [[0, 0, 0, 0] for _ in range(N - 3)]

l = 1
for r in range(2, N - 1):
    min_n = abs(psum(0, l) - psum(l, r))
    while True:
        if l + 1 < r and min_n > abs(psum(0, l + 1) - psum(l + 1, r)):
            min_n = abs(psum(0, l + 1) - psum(l + 1, r))
            l += 1
        else:
            break
    min_ns[r - 2][0] = psum(0, l)
    min_ns[r - 2][1] = psum(l, r)

a.reverse()
s = 0
for i, n in enumerate(a):
    s += n
    ss[i + 1] = s

l = 1
for r in range(2, N - 1):
    min_n = abs(psum(0, l) - psum(l, r))
    while True:
        if l + 1 < r and min_n > abs(psum(0, l + 1) - psum(l + 1, r)):
            min_n = abs(psum(0, l + 1) - psum(l + 1, r))
            l += 1
        else:
            break
    min_ns[N - r - 2][2] = psum(0, l)
    min_ns[N - r - 2][3] = psum(l, r)

ans = INF
for l in min_ns:
    ans = min(ans, max(l) - min(l))
print(ans)

Solution (Python):

from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
Acum = list(accumulate([0] + A))

def cumsum(left, right):
    
    return Acum[right] - Acum[left]

def find_best_cut(left, right, prev):
    prev = max(prev, left+1)
    now = prev
    res = now
    best = abs(cumsum(left, prev) - cumsum(prev, right))
    while True:
        now += 1
        score = abs(cumsum(left, now) - cumsum(now, right))
        if score < best:
            best = score
            res = now
        else:
            return res

left = 0
right = 0
best = float('inf')
for center in range(1, N-1):
    
    left = find_best_cut(0, center, left)
    right = find_best_cut(center, N, right)
    
    t = [cumsum(0, left), cumsum(left, center), cumsum(center, right), cumsum(right, N)]
    score = max(t) - min(t)
    if score < best:
        best = score
    
print(best)

Solution (Python):

from bisect import bisect_left
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]

num=10**14
for i in range(2,N-1):
    ans=[]
    x=(A[i]+A[0])/2
    j=bisect_left(A,x)
    
    if A[j]-x>x-A[j-1]:
        j-=1
    ans+=[A[j]-A[0],A[i]-A[j]]
    y=(A[N]+A[i])/2
    k=bisect_left(A,y)
    
    if A[k]-y>y-A[k-1]:
        k-=1
    ans+=[A[N]-A[k],A[k]-A[i]]
    
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Solution (Python):

from bisect import bisect_left
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]

num=10**14
for i in range(2,N-1):
    ans=[]
    x=(A[i]+A[0])/2
    j=bisect_left(A,x)
    
    if A[j]-x>x-A[j-1]:
        j-=1
    ans+=[A[j]-A[0],A[i]-A[j]]
    y=(A[N]+A[i])/2
    k=bisect_left(A,y)
    
    if A[k]-y>y-A[k-1]:
        k-=1
    ans+=[A[N]-A[k],A[k]-A[i]]
    
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Solution (Python):
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = LI()
    b = [a[0]]
    for c in a[1:]:
        b.append(b[-1]+c)
    d = [0] * n
    d[-1] = a[-1]
    for i in range(n-2,-1,-1):
        d[i] = d[i+1] + a[i]

    g = [[] for _ in range(n)]
    g[0] = [0,inf]
    j = 0
    for i in range(1,n):
        t = b[i]
        k = abs((b[i] - b[j]) - b[j])
        while j < i-1 and k > abs((b[i] - b[j+1]) - b[j+1]):
            k = abs((b[i] - b[j+1]) - b[j+1])
            j += 1
        g[i].append(b[j])
        g[i].append(b[i] - b[j])

    g[-1] = [0,inf]
    g[-2] = [0,inf]
    j = n-1
    for i in range(n-2,-1,-1):
        t = d[i]
        k = abs((d[i] - d[j]) - d[j])
        while j > i+1 and k > abs((d[i] - d[j-1]) - d[j-1]):
            k = abs((d[i] - d[j-1]) - d[j-1])
            j -= 1
        g[i-1].append(d[i] - d[j])
        g[i-1].append(d[j])

    r = inf
    for i in range(n):
        t = max(g[i]) - min(g[i])
        if r > t:
            r = t

    return r



print(main())

Solution (Python):
from bisect import bisect_left
from itertools import accumulate

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

cumsum = list(accumulate(A))
cumsum.insert(0, 0)

ans = float('inf')

for m in range(2, N-1):
    
    Lmid = cumsum[m] / 2
    Lx = bisect_left(cumsum, Lmid)

    
    if abs(Lmid - cumsum[Lx]) > abs(Lmid - cumsum[Lx-1]):
        Lx -= 1


    
    Rmid = (cumsum[m] + cumsum[N]) / 2
    Rx = bisect_left(cumsum, Rmid)

    
    if abs(Rmid - cumsum[Rx]) > abs(Rmid - cumsum[Rx-1]):
        Rx -= 1

    P, Q, R, S = cumsum[Lx], cumsum[m]-cumsum[Lx], cumsum[Rx]-cumsum[m], cumsum[N]-cumsum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

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

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ps = [None] * (N+1)
qs = [None] * (N+1)
rs = [None] * (N+1)
ss = [None] * (N+1)

l = 1
for r in range(2,N-1):
    p1 = cums[l]
    q1 = cums[r] - cums[l]
    d1 = abs(p1-q1)
    while l < r:
        p2 = cums[l+1]
        q2 = cums[r] - cums[l+1]
        d2 = abs(p2-q2)
        if d2 > d1: break
        l += 1
        p1,q1,d1 = p2,q2,d2
    ps[r] = p1
    qs[r] = q1

r = N-1
for l in range(N-2,1,-1):
    r1 = cums[r] - cums[l]
    s1 = cums[N] - cums[r]
    d1 = abs(r1-s1)
    while l < r:
        r2 = cums[r-1] - cums[l]
        s2 = cums[N] - cums[r-1]
        d2 = abs(r2-s2)
        if d2 > d1: break
        r -= 1
        r1,s1,d1 = r2,s2,d2
    rs[l] = r1
    ss[l] = s1

ans = cums[-1] * 999
for p,q,r,s in zip(ps,qs,rs,ss):
    if p is None: continue
    tmp = max(p,q,r,s) - min(p,q,r,s)
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]
f = lambda x:abs(x[0]-x[1])
def it():
  k1 = 1
  k2 = 3
  for i in range(2,N-1):
    ci = C[i]
    k1 = bisect(C, ci//2, lo=k1,hi=i)
    a,b = min(((ci-c,c) for c in (C[k1-1],C[k1])), key=f)
    k2 = bisect(C, (S+ci)//2, lo=k2,hi=N)
    c,d = min(((S-c,c-ci) for c in (C[k2-1],C[k2])), key=f)
    yield max(a,b,c,d)-min(a,b,c,d)

print(min(it()))

Solution (Python):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]

def it():
  k1 = 1
  k2 = 3
  for i in range(2,N-1):
    ci = C[i]
    k1 = bisect(C, ci//2, lo=k1,hi=i)
    _,a,b = min((abs(ci-2*c),ci-c,c) for c in (C[k1-1],C[k1]))
    k2 = bisect(C, (S+ci)//2, lo=k2,hi=N)
    _,c,d = min((abs(ci+S-2*c),S-c,c-ci) for c in (C[k2-1],C[k2]))
    yield max(a,b,c,d)-min(a,b,c,d)

print(min(it()))

Solution (Python):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))
S = C[N]

def solve(x):
  cx = C[x]
  k = bisect(C, cx//2, lo=1,hi=x)
  _,a,b = min((abs(cx-2*c),cx-c,c) for c in (C[k-1],C[k]))
  k = bisect(C, (S+cx)//2, lo=x+1,hi=N)
  _,c,d = min((abs(cx+S-2*c),S-c,c-cx) for c in (C[k-1],C[k]))
  L = (a,b,c,d)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-1)))

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

def left_list(a):
  i = 1
  left_sum = a[0] + a[1]
  left_1 = a[0]
  left = []
  left.append([a[0], a[1]])
  for j in range(2, n-2):
    left_sum += a[j]
    while 2 * (left_1 + a[i]) <= left_sum:
      left_1 += a[i]
      i += 1
    diff = left_sum - 2 * left_1
    diff_1 = 2 * (left_1 + a[i]) - left_sum
    if diff_1 < diff:
      left_1 += a[i]
      i += 1
    left.append([left_1, left_sum-left_1])
  
  return left

left_t = left_list(a)
a = a[::-1]
right_t = left_list(a)
right_t = right_t[::-1]
res = sum(a)
for x, y in zip(left_t, right_t):
  diff = max(max(x), max(y)) - min(min(x), min(y))
  if diff < res:
    res = diff
print(res)

Solution (Python):
from itertools import accumulate


from bisect import bisect_right, bisect_left

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


cumsum = list(accumulate(A))
cumsum.insert(0, 0)  


ans = float('inf')

for i in range(2, N-1):  
    
    Lmid = cumsum[i] / 2

    
    Lx = bisect_left(cumsum, Lmid)

    
    
    if abs(cumsum[Lx-1] - Lmid) < abs(cumsum[Lx] - Lmid):
        Lx -= 1


    
    Rmid = (cumsum[N] + cumsum[i]) / 2  
    Rx = bisect_left(cumsum, Rmid)
    
    if abs(cumsum[Rx-1] - Rmid) < abs(cumsum[Rx] - Rmid):
        Rx -= 1


    
    P = cumsum[Lx]

    
    Q = cumsum[i]-cumsum[Lx]

    
    R = cumsum[Rx]-cumsum[i]

    
    S = cumsum[N]-cumsum[Rx]
    
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_right, bisect_left

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


cumsum = list(accumulate(A))
cumsum.insert(0, 0)  


ans = float('inf')

for i in range(2, N-1):
    
    
    LC = cumsum[i] / 2

    LX = bisect_left(cumsum, LC)
    
    
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_left(cumsum, RC)
    
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

    P, Q, R, S = cumsum[LX], cumsum[i]-cumsum[LX], cumsum[RX]-cumsum[i], cumsum[N]-cumsum[RX]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)

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


cumsum = list(accumulate(A))
cumsum.insert(0, 0)


ans = float('inf')

for i in range(2, N-1):
    
    
    LC = cumsum[i] / 2

    LX = bisect_right(cumsum, LC)
    
    
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_right(cumsum, RC)
    
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

    P, Q, R, S = cumsum[LX], cumsum[i]-cumsum[LX], cumsum[RX]-cumsum[i], cumsum[N]-cumsum[RX]
    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()))
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)

Solution (Python):
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 1, cut + 2):
    if head <= i < end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if score > abs(a - b):
        score = abs(a - b)
        reta, retb = a, b
  return (reta, retb)

n = int(input())
acc = [0]
acc += accumulate(map(int, input().split()))

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

Solution (Python):
from bisect import bisect_left as bl
from itertools import accumulate
INF = 10 ** 20

def get_score(acc, head, end):
  sec_head = acc[head - 1]
  sec_end = acc[end]
  sec_sum = sec_end - sec_head
  cut = bl(acc, sec_head + sec_sum // 2) - 1
  score = INF
  reta, retb = None, None
  for i in range(cut - 2, cut + 3):
    if head <= i < end: 
      a = acc[i] - sec_head
      b = sec_end - acc[i]
      if score > abs(a - b):
        score = abs(a - b)
        reta, retb = a, b
  return (reta, retb)

n = int(input())
acc = [0]
acc += accumulate(map(int, input().split()))

ans = INF
for i in range(2, n - 1):
  p, q = get_score(acc, 1, i)
  r, s = get_score(acc, i + 1, n)
  if not None in (p, q, r, s):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
print(ans)

Solution (Python):
from functools import reduce

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = reduce(lambda x, y: x + y, a[3:])
temp = right + 1
res_right = abs(s - r)
x = r
y = s
while temp < n - 1:
    x += a[temp]
    y -= a[temp]
    if abs(x - y) < res_right:
        right = temp
        r = x
        s = y
        res_right = abs(x - y)
    if x >= y:
        break
    temp += 1
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)

Solution (Python):
import functools
N = int(input())
A = [int(x) for x in input().split()]
P = A[0]
Q = A[1]
R = A[2]
S = functools.reduce(lambda x, y: x + y, A[3:])
i = 1
k = 3
SR_pre = abs(S - R)
for m in range(k, N - 1):
  SR_post = abs(S - R - 2 * A[m])
  if SR_post <= SR_pre:
    SR_pre = SR_post
    R += A[m]
    S -= A[m]
    k = m + 1
  else:
    break
ans = max(P, Q, R, S) - min(P, Q, R, S)
for j in range(2, N - 2):
  Q += A[j]
  QP_pre = abs(Q - P)
  for l in range(i, j):
    QP_post = abs(Q - P - 2 * A[l])
    if QP_post <= QP_pre:
      QP_pre = QP_post
      P += A[l]
      Q -= A[l]
      i = l + 1
    else:
      break
  R -= A[j]
  SR_pre = abs(S - R)
  for m in range(k, N - 1):
    SR_post = abs(S - R - 2 * A[m])
    if SR_post <= SR_pre:
      SR_pre = SR_post
      R += A[m]
      S -= A[m]
      k = m + 1
    else:
      break
  ans = min(ans, max(P,Q, R, S) - min(P, Q, R, S))
print(ans)

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


AA = [0  for x in range(N)]
for i,a in enumerate(A):
    AA[i] = AA[i-1] + a
ans = 99999999999999999
ed = 2
st = 0
_bc = AA[-1]
_de = AA[-1]

for i in range(1, N-1):
    med = AA[i] / 2
    j = bisect(AA, med)
    if abs(AA[j-1] - med) < abs(AA[j] - med):
        j = j-1
    rmed = (AA[-1] + AA[i]) / 2
    k = bisect(AA, rmed)
    if abs(AA[k-1] - rmed) < abs(AA[k] - rmed):
        k = k-1
    m = min(AA[j], AA[i] - AA[j], AA[k] - AA[i], AA[-1] - AA[k])
    M = max(AA[j], AA[i] - AA[j], AA[k] - AA[i], AA[-1] - AA[k])
    ans = min(ans, M - m)
print(ans)

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

pre = [0]
for i in range(1,N+1):
    pre.append(pre[i-1] + A[i-1])

L = 1
r = 3
ans = 10**18
        
for i in range(2,N-1):
    while L + 1 < i and abs(pre[L+1] - pre[i] + pre[L+1]) < abs(pre[L] - pre[i] + pre[L]):
        L += 1

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

    ans = min(ans,max(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]) - \
          min(pre[L],pre[i]-pre[L],pre[r]-pre[i],pre[N]-pre[r]))

print(ans)

Solution (Python):

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


a = 0
A_left = []
for i in range(n):
    a += A_list[i]
    A_left.append(a)
    
res = A_left[n-1]
i = 0
j = 1
k = 2
while j <= n - 3:
    while True:
        if abs(A_left[j] / 2 - A_left[i]) > abs(A_left[j] / 2 - A_left[i+1]):
            i += 1
        else:
            break
            
    while True:
        if abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k])) > abs((A_left[n-1] - A_left[j]) / 2 - (A_left[n-1] - A_left[k+1])):
            k += 1
        else:
            break
    
    a, b, c, d = A_left[i], A_left[j]-A_left[i], A_left[k]-A_left[j], A_left[n-1]-A_left[k]
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
    j += 1
    
print(res)

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

ans = float('inf')
i1, i3 = 1, 3
s = [aaa[0], aaa[1], aaa[2], sum(aaa[3:])]
for i2 in range(2, n - 1):
    if i2 == i3:
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    while i1 < i2 - 1 and abs(s[0] - s[1]) > abs(s[0] - s[1] + 2 * aaa[i1]):
        s[0] += aaa[i1]
        s[1] -= aaa[i1]
        i1 += 1
    while i3 < n - 1 and abs(s[2] - s[3]) > abs(s[2] - s[3] + 2 * aaa[i3]):
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    ans = min(ans, max(s) - min(s))
    s[1] += aaa[i2]
    s[2] -= aaa[i2]

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

def solve(x):
  L = h(0,x)+h(x,N)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-1)))

Solution (Python):

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


a = 0
A_left = []
for i in range(N):
    a += A_list[i]
    A_left.append(a)
    

a = 0
A_right = []
for i in range(N):
    a += A_list[N-1-i]
    A_right.append(a)

def binary_search_left(s):
    m = 0
    l = 0
    r = N - 1
    
    if A_left[0] > s:
        return 0
    
    while True:
        m = (l + r) // 2
        
        if A_left[m] <= s and A_left[m+1] > s:
            break
        elif A_left[m] <= s:
            l = m
        else:
            r = m
    if s - A_left[m] <= A_left[m+1] - s:
        return m
    else:
        return m+1
    
def binary_search_right(s):
    m = 0
    l = 0
    r = N - 1
    
    if A_right[0] > s:
        return 0
    
    while True:
        m = (l + r) // 2
        
        if A_right[m] <= s and A_right[m+1] > s:
            break
        elif A_right[m] <= s:
            l = m
        else:
            r = m
    if s - A_right[m] <= A_right[m+1] - s:
        return m
    else:
        return m+1
    

res = A_left[N-1]
for s in range(2, N-1):
    
    m_l = binary_search_left(A_left[s-1]/2)
    a, b = A_left[m_l], A_left[s-1] - A_left[m_l]
    r = N - s 
    m_r = binary_search_right(A_right[r-1]/2)
    c, d = A_right[m_r], A_right[r-1] - A_right[m_r]
    
    r = max([a,b,c,d]) - min([a,b,c,d])
    if r < res:
        res = r
if N == 4:
    res = max(A_list) - min(A_list)
print(res)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


N = int(input())
A = [0] + list(map(int, input().split()))


def check(mid, base): 
    if mid < base:
        l = imos[mid-1]
        r = imos[base-1] - imos[mid-1]
        return abs(r-l)
    else:
        l = imos[mid] - imos[base-1]
        r = imos[N] - imos[mid]
        return abs(r-l)
        
        

def ternarySearchInt(small, big, i):
    if big - small <= 2:  
        mid = (big + small) // 2
        if check(big, i) <= check(mid, i):
            return big
        else:
            return small if check(small, i) <= check(mid, i) else mid
    else:
        midl = (big + small) // 2
        midr = midl + 1
        if check(midl, i) >= check(midr, i):
            return ternarySearchInt(midl, big, i)
        else:
            return ternarySearchInt(small, midr, i)



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

ans = int(1e18)
for i in range(3, N):
    l = ternarySearchInt(1, i-1, i)
    r = ternarySearchInt(i, N, i)
    P = imos[l-1]
    Q = imos[i-1] - P
    R = imos[r] - imos[i-1]
    S = imos[N] - imos[r]
    hoge = [P,Q,R,S]
    ans = min(ans, max(hoge) - min(hoge))


print(ans)

Solution (Python):

def section_sum(a, b):
    return acc[b] - acc[a]


def minimize(s1, s2, s3):
    lsum = float("inf")
    for i in range(s1, s2):
        if abs(section_sum(0, i) - section_sum(i, s2)) < lsum:
            q = section_sum(0, i)
            r = section_sum(i, s2)
            s1 = i
            lsum = abs(q - r)
        else:
            break

    rsum = float("inf")
    for i in range(s3, len(a)):
        if abs(section_sum(s2, i) - section_sum(i, len(a))) < rsum:
            s = section_sum(s2, i)
            t = section_sum(i, len(a))
            s3 = i
            rsum = abs(s - t)
        else:
            break

    cut = [q, r, s, t]
    return abs(min(cut) - max(cut)), s1, s2, s3


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

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

s1, s2, s3 = 1, 2, 3
ans = float("inf")
for s2 in range(2, len(a) - 1):
    x, s1, s2, s3 = minimize(s1, s2, s3)
    ans = min(ans, x)

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_right

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

accAs = [0] + list(accumulate(As))


def getSum(iFr, iTo):
    return accAs[iTo+1] - accAs[iFr]



def getDivision(iFr, iTo):
    sumB = getSum(iFr, iTo)
    iMid = bisect_right(accAs, accAs[iFr]+sumB/2, iFr+1, iTo+2) - 1

    diff1, diff2 = float('inf'), float('inf')
    if iMid != iFr:
        sum1L = getSum(iFr, iMid-1)
        sum1R = getSum(iMid, iTo)
        diff1 = abs(sum1L - sum1R)
    if iMid != iTo:
        sum2L = getSum(iFr, iMid)
        sum2R = getSum(iMid+1, iTo)
        diff2 = abs(sum2L - sum2R)

    return [sum1L, sum1R] if diff1 <= diff2 else [sum2L, sum2R]



ans = float('inf')
for iMid in range(1, N-3+1):
    sumD = []
    sumD += getDivision(0, iMid)
    sumD += getDivision(iMid+1, N-1)

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

print(ans)

Solution (Python):
from bisect import bisect
n = int(input())
a = [int(x) for x in input().split()]
 
r = 0
s = []
for i in a:
  r += i
  s.append(r)

def bs(x,y):
  b = bisect(x, y)
  if abs(x[b-1] - y) < abs(x[b] - y):
    b = b-1
  return b
 
m = 10**20
for i in range(1, n-1):
  k = bs(s, s[i] / 2)
  l = bs(s, (s[n-1] + s[i]) / 2)
  s4 = [s[k],s[i]-s[k],s[l]-s[i],s[n-1]-s[l]]
  m = min(m, max(s4) - min(s4))

print(m)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


N = int(input())
A = [0] + list(map(int, input().split()))


def check(mid, base): 
    if mid < base:
        l = imos[mid-1]
        r = imos[base-1] - imos[mid-1]
        return abs(r-l)
    else:
        l = imos[mid] - imos[base-1]
        r = imos[N] - imos[mid]
        return abs(r-l)
        
        

def ternarySearchInt(small, big, i):
    
    if small == big:
        return small
    elif big - small == 1:
        if check(small, i) <= check(big, i):
            return small
        else:
            return big

    def func(small, big):
        midl = (big + small) // 2
        midr = midl + 1
        if big - small == 2:  
            mid = midl
            if check(small, i) <= check(mid, i):
                if check(small, i) <= check(big, i):
                    return small
                else:
                    return big
            else:
                if check(mid, i) <= check(big, i):
                    return mid
                else:
                    return big
        else:
            if check(midl, i) > check(midr, i):
                return func(midl, big)
            else:
                return func(small, midr)
    return func(small, big)



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

ans = int(1e18)
for i in range(3, N):
    l = ternarySearchInt(1, i-1, i)
    r = ternarySearchInt(i, N, i)
    P = imos[l-1]
    Q = imos[i-1] - P
    R = imos[r] - imos[i-1]
    S = imos[N] - imos[r]
    hoge = [P,Q,R,S]
    ans = min(ans, max(hoge) - min(hoge))


print(ans)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

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

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

def search(s, prev_S, l=0, r=N):
    
    if r-l <= 1:
        return l
    m = l + (r-l)//2
    if S[m] - prev_S > s:
        return search(s, prev_S, l, m)
    else:
        return search(s, prev_S, m, r)


min_ = 10**20
for i in range(1, N-2):
    if i == 3:
        flag = True
    else:
        flag = False
    li = search(S[i]/2, 0, 0, i+1)
    ri = search((S[N-1]-S[i])/2, S[i], i+1, N)
    candidates = [(li, i, ri),   (li+1, i, ri),
                  (li, i, ri+1), (li+1, i, ri+1)]
    for p, q, r in candidates:
        
        if r >= N:
            continue
        P = S[p]
        Q = S[q] - S[p]
        R = S[r] - S[q]
        S_ = S[N-1] - S[r]
        cur_min = min(P, Q, R, S_)
        cur_max = max(P, Q, R, S_)
        min_ = min(min_, cur_max-cur_min)
    

print(min_)

Solution (Python):

from bisect import bisect, bisect_left
from itertools import accumulate, product

N = int(input())
A = list(map(int, input().split()))
S = list(accumulate(A))
T = sum(A)
ans = 10**16

for j in range(1, N-1):
    PQ = S[j]
    RS = T - S[j]
    
    
    i1 = bisect(S, PQ/2) - 1
    i2 = bisect_left(S, PQ/2)
    
    k1 = bisect(S, RS/2 + PQ) - 1
    k2 = bisect_left(S, RS/2 + PQ)
    
    for i, k in product([i1, i2], [k1, k2]):
        
        if i < 0 or i==j or j == k or k == N-1:
            continue
        PQRS = [S[i], S[j] - S[i], S[k] - S[j], T - S[k]]
        
        ans = min(ans, abs(max(PQRS) - min(PQRS)))

print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()

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



ans = 10**20
for i in range(2, N-1):
  lmid = psum[i] / 2
  k = bisect(psum, lmid)
  if abs(psum[k-1] - lmid) < abs(psum[k] - lmid):
    k = k-1

  rmid = (psum[N] + psum[i]) / 2
  l = bisect(psum, rmid)
  if abs(psum[l-1] - rmid) < abs(psum[l] - rmid):
    l = l-1

  m = min(psum[k], psum[i] - psum[k], psum[l] - psum[i], psum[N] - psum[l])
  M = max(psum[k], psum[i] - psum[k], psum[l] - psum[i], psum[N] - psum[l])
  ans = min(ans, M - m)

print(ans)