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())
n = N

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

s = [0]
ans = float("inf")

for i in range(N):
    s.append(s[-1] + A[i])

for i in range(N-3):

    i += 1

    l = 0
    r = i+1

    while r-l != 1:

        m = (l+r) // 2
        if s[m] <= s[i+1] / 2:
            l = m
        else:
            r = m

    if l == 0:
        b = s[1]
        c = s[i+1] - b
    elif r == i+1:
        b = s[i]
        c = s[i+1]-s[i]
    elif abs(s[l] - s[i+1]/2) < abs(s[r] - s[i+1]/2):
        b = s[l]
        c = s[i+1]-s[l]
    else:
        b = s[r]
        c = s[i+1]-s[r]

    l = i+1
    r = n

    while r-l != 1:

        m = (l+r) // 2
        if s[m]-s[i+1] <= (s[n]-s[i+1])/2:
            l = m
        else:
            r = m

    if l == i+1:
        d = s[i+2]-s[i+1]
        e = s[n] - s[i+2]
    elif r == n:
        d = s[n-1]-s[i+1]
        e = s[n]-s[n-1]
    elif abs((s[l]-s[i+1]) - (s[n]-s[i+1])/2) < abs((s[r]-s[i+1]) - (s[n]-s[i+1])/2):
        d = s[l]-s[i+1]
        e = s[n]-s[l]
    else:
        d = s[r]-s[i+1]
        e = s[n]-s[r]

    ans = min(ans, max(b,c,d,e) - min(b,c,d,e))

print (ans)

Solution (Python):
def examC():
    N = I()
    A = LI()
    Ad = [0]*N
    for i in range(N):
        Ad[i] = A[i]-(i+1)
    Ad.sort()

    b = Ad[N//2]
    ans = 0
    for a in Ad:
        ans +=abs(a-b)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    cumA = [0]*N
    cumA[0] = A[0]
    for i in range(N-1):
        cumA[i+1] = cumA[i]+A[i+1]
    ans = inf

    for i in range(1,N-1):
        curcd = (cumA[i]+1)//2
        cd = bisect.bisect_right(cumA,curcd)

        C = cumA[cd]; D = cumA[i]-C
        if cd>0 and abs(C-D)>abs(cumA[cd-1]-(cumA[i]-cumA[cd-1])):
            C = cumA[cd-1]; D = cumA[i] - C
        curef = (cumA[-1]-cumA[i]+1)//2
        ef = bisect.bisect_right(cumA,curef+cumA[i])

        E = cumA[ef]-cumA[i]; F = cumA[-1]-E-cumA[i]
        if abs(E-F)>abs(cumA[ef-1]-cumA[i]-(cumA[-1]-cumA[ef-1])):
            E = cumA[ef-1]-cumA[i]; F = cumA[-1]-E-cumA[i]
 
        ansC = max(C,D,E,F)-min(C,D,E,F)
        ans = min(ans,ansC)
 
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examD()

Solution (Python):
import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())



csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)


mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    
    for i in range(mid0, mid1):
        
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)

Solution (Python):
import sys
import itertools
import bisect

readInt = lambda : [int(i) for i in input().split()];
n = readInt()[0]
A = readInt()

B = list(itertools.accumulate(A))

cand = 2 * pow(10, 14)
for i in range(2, len(A)-1):
  z = B[i-1]
  s = z // 2
  j = bisect.bisect_right(B, s)
  if (j == 0):
    j0 = j
  else:
    c0 = abs(2 * B[j-1] - z)
    c1 = abs(2 * B[j] - z)
    j0 = j-1 if c0 < c1 else j

  z = B[-1]
  s = B[i-1] + (B[-1] - B[i-1]) // 2
  j = bisect.bisect_right(B, s)
  if (j == i):
    j1 = j
  else:
    c0 = abs(B[j-1] - B[i-1] - (B[-1] - B[j-1]))
    c1 = abs(B[j]   - B[i-1] - (B[-1] - B[j]  ))
    j1 = j-1 if c0 < c1 else j

  c = [B[j0], B[i-1] - B[j0], B[j1] - B[i-1], B[-1] - B[j1]]
  cand = min(cand, max(c) - min(c))

ans = cand
print(ans)

Solution (Python):
def main():
    from itertools import accumulate as ac
    from bisect import bisect_right as br
    n=int(input())
    a=list(map(int,input().split()))
    b=list(ac([0]+a))
    ans=[]
    for i in range(2,n-1):
        l=b[i]
        r=b[n]
        lc=br(b,l/2)
        rc=br(b,l+(r-l)/2)
        temp_l=[]
        temp_r=[]
        if lc>1:
            temp_l.append([b[lc-1],l-b[lc-1]])
        if lc<i:
            temp_l.append([b[lc],l-b[lc]])
        if rc>i+1:
            temp_r.append([b[rc-1]-l,r-b[rc-1]])
        if rc<n:
            temp_r.append([b[rc]-l,r-b[rc]])
        temp_l.sort(key=lambda x:abs(x[0]-x[1]))
        temp_r.sort(key=lambda x:abs(x[0]-x[1]))
        temp=temp_l[0]+temp_r[0]
        temp.sort()
        ans.append(temp[-1]-temp[0])
    print(min(ans))
main()

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

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

S = [A[0], A[1], A[2], sum(A[3:])]
l = 0
r = 2
while r < N-1:
    if S[2] + A[r+1] <= S[3] - A[r+1]:
        S[2] += A[r+1]
        S[3] -= A[r+1]
        r += 1
    else:
        break

S2 = [S[0], S[1], S[2]+A[r+1], S[3]-A[r+1]]
ans = min(max(S)-min(S), max(S2)-min(S2))
for m in range(2, N-2):
    S[1] += A[m]
    S[2] -= A[m]
    while r < N-1:
        if S[2] + A[r+1] <= S[3] - A[r+1]:
            S[2] += A[r+1]
            S[3] -= A[r+1]
            r += 1
        else:
            break
    
    while l < m:
        if S[0] + A[l+1] <= S[1] - A[l+1]:
            S[0] += A[l+1]
            S[1] -= A[l+1]
            l += 1
        else:
            break
    
    S1 = [S[0]+A[l+1], S[1]-A[l+1], S[2], S[3]]
    S2 = [S[0], S[1], S[2]+A[r+1], S[3]-A[r+1]]
    S3 = [S[0]+A[l+1], S[1]-A[l+1], S[2]+A[r+1], S[3]-A[r+1]]
    ans = min([ans, max(S)-min(S), max(S1)-min(S1), max(S2)-min(S2), max(S3)-min(S3)])

print(ans)

Solution (Python):
import bisect

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


def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P = min(P, B[i - 1])
		if x >= 1:
			P2 = max(B[x - 1], B[1])
			Q2 = Q - P2
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q -= P

		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R = min(R, B[N - 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S2 = S - R2
		if y < N:
			S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
			R3 = S - S3
		S -= R
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P3, Q3, R, S) - min(P3, Q3, R, S))
		ans = min(ans, max(P, Q, R2, S2) - min(P, Q, R2, S2))
		ans = min(ans, max(P3, Q3, R2, S2) - min(P3, Q3, R2, S2))
		if x >= 1:
			ans = min(ans, max(P2, Q2, R, S) - min(P2, Q2, R, S))
			ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		if y < N:
			ans = min(ans, max(P, Q, R3, S3) - min(P, Q, R3, S3))
			ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
		if x >= 1 and y < N:
			ans = min(ans, max(P2, Q2, R3, S3) - min(P2, Q2, R3, S3))
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
Ll, Lr, Rl, Rr = 0, A[0], A[1], sum(A[2:])
idx_l = 0  
idx_r = 2  
ans = float("inf")
for i, a in enumerate(A[1:-2], 1):
    Lr += a
    Rl -= a
    while True:
        a_ = A[idx_l]
        if abs((Ll+a_)-(Lr-a_)) < abs(Ll-Lr):
            Ll += a_
            Lr -= a_
            idx_l += 1
        else:
            break
    while True:
        a_ = A[idx_r]
        if abs((Rl+a_)-(Rr-a_)) < abs(Rl-Rr):
            Rl += a_
            Rr -= a_
            idx_r += 1
        else:
            break
    ans = min(ans, max(Ll, Lr, Rl, Rr)-min(Ll, Lr, Rl, Rr))
print(ans)

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

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

cumsum = (0,) + tuple(accumulate(a))





ans = cumsum[-1]
for cut in range(2, n - 1):
    
    
    
    

    sPQ = cumsum[cut]
    sRS = cumsum[n] - cumsum[cut]

    lc = bisect_left(cumsum, sPQ // 2)
    
    lc_1 = lc - 1
    

    if abs((sPQ - cumsum[lc]) - cumsum[lc]) < abs((sPQ - cumsum[lc_1]) - cumsum[lc_1]):
        sP = cumsum[lc]
        
    else:
        sP = cumsum[lc_1]
        
    sQ = sPQ - sP
    

    rc = bisect_left(cumsum, sPQ + (sRS // 2))
    
    rc_1 = rc - 1
    

    if abs((sRS - (cumsum[rc] - sPQ)) - (cumsum[rc] - sPQ)) < abs((sRS - (cumsum[rc_1] - sPQ)) - (cumsum[rc_1] - sPQ)):
        sR = cumsum[rc] - sPQ
        
    else:
        sR = cumsum[rc_1] - sPQ
        
    sS = sRS - sR
    

    t = (sP, sQ, sR, sS)

    ans = min(ans, max(t) - min(t))
    
print(ans)

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

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

def bisect(l,r,Su,il):
    while r-l>1:
        if S[(l+r)//2]-S[il] > Su//2:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return l

min_score = 10**27

for i in range(2,N-1):
    l1 = bisect(0,i,S[i],0)
    l2 = bisect(i,N,S[N]-S[i],i)
    P = S[l1]
    Q = S[i]-P
    R = S[l2]-S[i]
    S1 = S[N]-S[l2]
    val1 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1+1]
    Q = S[i]-P
    R = S[l2]-S[i]
    S1 = S[N]-S[l2]
    val2 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1]
    Q = S[i]-P
    R = S[l2+1]-S[i]
    S1 = S[N]-S[l2+1]
    val3 = max(P,Q,R,S1)-min(P,Q,R,S1)
    P = S[l1+1]
    Q = S[i]-P
    R = S[l2+1]-S[i]
    S1 = S[N]-S[l2+1]
    val4 = max(P,Q,R,S1)-min(P,Q,R,S1)
    min_score = min(val1,val2,val3,val4,min_score)

print(min_score)

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

N = int(input())
A = list(map(int, input().split()))
A = [0] + A
a = list(accumulate(A))
answer = a[-1]


for i in range(N - 3):
    left = a[i + 2]
    right = a[-1] - left
    p = bisect_left(a, left // 2)
    P1 = a[p]
    Q1 = left - P1
    P2 = a[p - 1]
    Q2 = left - P2
    if abs(P1 - Q1) <= abs(P2 - Q2):
        P = P1
        Q = Q1
    else:
        P = P2
        Q = Q2

    s = bisect_right(a, a[-1] - right // 2)
    S1 = a[-1] - a[s - 1]
    R1 = right - S1
    S2 = a[-1] - a[s]
    R2 = right - S2
    if abs(S1 - R1) <= abs(S2 - R2):
        S = S1
        R = R1
    else:
        S = S2
        R = R2

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

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, q, r, s = a[0], a[1], a[2], sum(a[3:])
    lb, rb = 1, 3
    ans = max(p, q, r, s) - min(p, q, r, s)
    for mb in range(2, n-1):
        if mb > 2:
            q += a[mb-1]
            r -= a[mb-1]
        if mb == rb:
            r = a[rb]
            s -= a[rb]
            rb += 1
        while lb+1 < mb and abs(q-p) >= abs(p+a[lb] - (q-a[lb])):
            p += a[lb]
            q -= a[lb]
            lb += 1
        while rb+1 < n and abs(s-r) >= abs(r+a[rb] - (s-a[rb])):
            r += a[rb]
            s -= a[rb]
            rb += 1
        ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
def input():
	return sys.stdin.readline().strip()

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

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

ans = 10**14

one = 0
three = 2
for i in range(1, N - 2):
	if three == i:
		three += 1
	sum_half1 = A_sum[i + 1]
	sum_half2 = A_sum[-1] - A_sum[i + 1]
	while one < i - 1:
		if abs(A_sum[one + 1] - sum_half1/2) > abs(A_sum[one + 2] - sum_half1/2):
			one += 1
		else:
			break
	while three < N - 2:
		if abs(A_sum[three + 1] - A_sum[i + 1] - sum_half2/2) > abs(A_sum[three + 2] - A_sum[i + 1] - sum_half2/2):
			three += 1
		else:
			break

	x = max(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	y = min(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	ans = min(ans, x - y)
	
print(ans)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(1, N-2):
    s1 = S1[i]
    b = bisect_left(S1, s1/2)
    if abs(S1[b]-s1/2)>abs(s1/2-S1[b-1]):
        b-=1
    P, Q = S1[b], s1-S1[b]
    s2 = S2[N-i-2]
    c = bisect_left(S2, s2/2)
    if abs(S2[c]-s2/2)>abs(s2/2-S2[c-1]):
        c-=1
    R, S = S2[c], s2-S2[c]
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)

Solution (Python):
def lower_bound(l, r, val):
    while r - l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + (0 if l == 0 else sum[l - 1]))
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)


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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp

ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            t = l1, r1, l2, r2
            ans = min(ans, max(t) - min(t))

print(ans)

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

tmp = 0
sum = [0 for i in range(N)]

for a, b in enumerate(A):
    tmp += b
    sum[a] = tmp


def search(l, r):
    mid = lower_bound(l, r + 1, get_sum(l, r) / 2 + (0 if l == 0 else sum[l-1]))
    for i in range(mid - 2, mid + 3):
        if l <= i and i + 1 <= r:
            yield get_sum(l, i), get_sum(i + 1, r)










def lower_bound(l, r, val):
    while r-l > 1:
        mid = (r + l) // 2
        if sum[mid] <= val:
            l = mid
        else:
            r = mid
    return l


def get_sum(l, r):
    return sum[r] - (0 if l == 0 else sum[l - 1])


ans = tmp

for ind in range(1, N - 2):
    for l1, r1 in search(0, ind):
        for l2, r2 in search(ind + 1, N - 1):
            
            
            t = l1, r1, l2, r2
            
            ans = min(ans, max(t) - min(t))
            
            

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
 
i, k = 0, 2
p, q, r, s = 0, a[0], a[1], sum(a[2:])
ans = sum(a)
for j in range(1, n-2):
    q += a[j]
    while abs((q-a[i]) - (p+a[i])) < abs(q - p):
        p += a[i]
        q -= a[i]
        i += 1
 
    r -= a[j]
    while abs((s-a[k]) - (r+a[k])) < abs(s - r):
        r += a[k]
        s -= a[k]
        k += 1
 
    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    
    
print(ans)

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

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

i, k = 0, 2
ans = 10**18
for j in range(1, n-2):
    while i < j:
        p = cumsum[i]
        q = cumsum[j] - cumsum[i]
        p_new = cumsum[i+1]
        q_new = cumsum[j] - cumsum[i+1]
        if abs(q_new - p_new) > abs(q - p):
            break
        else:
            i += 1

    while k < n-1:
        r = cumsum[k] - cumsum[j]
        s = cumsum[n-1] - cumsum[k]
        r_new = cumsum[k+1] - cumsum[j]
        s_new = cumsum[n-1] - cumsum[k+1]
        if abs(s_new - r_new) > abs(s - r):
            break
        else:
            k += 1

    pqrs = [p, q, r, s]
    ans = min(ans, abs(max(pqrs) - min(pqrs)))
    
    
print(ans)

Solution (Python):
import bisect
N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
    B.append(A[i]+B[i-1])


ans=10**20
for x in range(2,N-1):
    
    Q=[]
    q1=B[bisect.bisect_left(B,B[x-1]/2)]
    q2=B[x-1]-q1
    q3=B[bisect.bisect_left(B,B[x-1]/2)-1]
    q4=B[x-1]-q3
    if abs(q1-q2)<abs(q3-q4):
        Q.append(q1)
        Q.append(q2)
    else:
        Q.append(q3)
        Q.append(q4)
    q5=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)]-B[x-1]
    q6=B[N-1]-q5-B[x-1]
    q7=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)-1]-B[x-1]
    q8=B[N-1]-q7-B[x-1]
    
    if abs(q5-q6)<abs(q7-q8):
        Q.append(q5)
        Q.append(q6)
    else:
        Q.append(q7)
        Q.append(q8)
    if (max(Q)-min(Q))<ans:
        ans=(max(Q)-min(Q))
    
print(ans)

Solution (Python):
N=int(input())
inlis=[int(i) for i in input().split()]
csum=[0]*(N+1)
for i, v in enumerate(inlis, start=1): csum[i] = csum[i-1] + v
i, k = 1, 3
resmin = 9223372036854775807
for j in range(2, N-1):
    while abs((csum[i]-csum[0]) - (csum[j]-csum[i])) > abs((csum[i+1]-csum[0]) - (csum[j]-csum[i+1])): i += 1
    while abs((csum[k]-csum[j]) - (csum[N]-csum[k])) > abs((csum[k+1]-csum[j]) - (csum[N]-csum[k+1])): k += 1
    resmin = min(resmin, max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))
print(resmin)

Solution (Python):
N=int(input())
inlis=[int(i) for i in input().split()]
csum=[0]*(N+1)
for i, v in enumerate(inlis, start=1): csum[i] = csum[i-1] + v

i, k = 1, 3
resmin = 9223372036854775807

for j in range(2, N-1):
    while abs((csum[i]-csum[0]) - (csum[j]-csum[i])) > abs((csum[i+1]-csum[0]) - (csum[j]-csum[i+1])): i += 1
    while abs((csum[k]-csum[j]) - (csum[N]-csum[k])) > abs((csum[k+1]-csum[j]) - (csum[N]-csum[k+1])): k += 1
    
    
    
    resmin = min(resmin, max(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]) - min(csum[i]-csum[0], csum[j]-csum[i], csum[k]-csum[j], csum[N]-csum[k]))

print(resmin)

Solution (Python):
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()
aa = [a[0]]

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

ans = Max
l = 0
r = 2
s = aa[1]
su = aa[-1]-s
for i in range(1,n-1):
	while(l < i and (s >= abs(2*aa[l] - aa[i]))):
		s =  abs(2*aa[l] - aa[i])
		l += 1

	while(r < n and (su >= abs(aa[-1]-aa[r]-(aa[r] - aa[i])))):
		su = abs(aa[-1]-aa[r]-(aa[r] - aa[i]))
		r += 1
	ans = min(ans,(max(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1]) - min(aa[l-1],aa[i]-aa[l-1],aa[r-1]-aa[i],aa[-1]-aa[r-1])))
	s = abs(2*aa[l-1] - aa[i+1])
	su = abs(aa[-1]-aa[r-1]-(aa[r-1] - aa[i+1]))


print(ans)

Solution (Python):


import sys
from itertools import accumulate
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

cmsm=[0]+list(accumulate(A))
ans=INF
for i in range(2, N-1):
    
    S1=cmsm[i]
    idx1=bisect_left(cmsm, S1/2)
    
    if abs(cmsm[idx1-1]-S1/2)<abs(cmsm[idx1]-S1/2):
        idx1-=1

    
    S2=cmsm[N]-cmsm[i]
    idx2=bisect_left(cmsm, S1+S2/2)
    if abs(cmsm[idx2-1]-(S1+S2/2))<abs(cmsm[idx2]-(S1+S2/2)):
        idx2-=1

    p=cmsm[idx1]-cmsm[0]
    q=cmsm[i]-cmsm[idx1]
    r=cmsm[idx2]-cmsm[i]
    s=cmsm[N]-cmsm[idx2]
    mx=max(p, q, r, s)
    mn=min(p, q, r, s)
    ans=min(ans, mx-mn)
print(ans)

Solution (Python):
import bisect
def inpl(): return list(map(int,input().split()))

N = int(input())
A = inpl()

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

mindiff = cum[N-1]
for j in range(2,N-1):
    sum1 = cum[j-1]
    sum2 = cum[N-1]-cum[j-1]
    i = bisect.bisect_left(cum, sum1/2)
    k = bisect.bisect_left(cum, sum1 + sum2/2)
    if i == 0:
        max1 = A[0]
        min1 = cum[j-1]-A[0]
    elif j == 2:
        max1 = A[1]
        min1 = A[0]
    else:
        max1 = min(cum[i],cum[j-1]-cum[i-1])
        min1 = max(cum[i-1],cum[j-1]-cum[i])

    if k == j:
        max2 = A[j]
        min2 = cum[N-1]-cum[j]
    elif j == N-2:
        max2 = A[N-1]
        min2 = A[N-2]
    else:
        max2 = min(cum[k]-cum[j-1],cum[N-1]-cum[k-1])
        min2 = max(cum[k-1]-cum[j-1],cum[N-1]-cum[k])

    max3 = max(max1,max2)
    min3 = min(min1,min2)
    mindiff = min(mindiff, max3-min3)

print(mindiff)

Solution (Python):
from bisect import bisect, bisect_left

n = int(input())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append(b[-1] + a[i])

ans = float("inf")
for j in range(2, n-1):
	c = []
	f = bisect(b, b[j]/2)
	f -= 1
	if f == 0 or j == 2:
		c += [b[1]-b[0], b[j]-b[1]]
	elif f == j-1:
		c += [b[j-1]-b[0], b[j]-b[j-1]]
	else:
		if abs(b[f]-b[0] - (b[j]-b[f])) <= abs(b[f+1]-b[0] - (b[j]-b[f+1])):
			c += [b[f]-b[0], b[j]-b[f]]
		else:
			c += [b[f+1]-b[0], b[j]-b[f+1]]

	l = bisect(b, b[j]+((b[n]-b[j])/2))
	l -= 1
	
	if l == j or j == n-2:
		c += [b[j+1]-b[j], b[n]-b[j+1]]
	elif l == n-1:
		c += [b[n-1]-b[j], b[n]-b[n-1]]
	else:
		if abs(b[l]-b[j] - (b[n]-b[l])) <= abs(b[l+1]-b[j] - (b[n]-b[l+1])):
			c += [b[l]-b[j], b[n]-b[l]]
		else:
			c += [b[l+1]-b[j], b[n]-b[l+1]]

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

print(ans)

Solution (Python):
from bisect import bisect, bisect_left

n = int(input())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append(b[-1] + a[i])

ans = float("inf")
for j in range(2, n-1):
	c = []
	f = bisect(b, b[j]/2)
	f -= 1
	if f == 0 or j == 2:
		c += [b[1]-b[0], b[j]-b[1]]
	elif f == j-1:
		c += [b[j-1]-b[0], b[j]-b[j-1]]
	else:
		if abs(b[f]-b[0] - (b[j]-b[f])) <= abs(b[f+1]-b[0] - (b[j]-b[f+1])):
			c += [b[f]-b[0], b[j]-b[f]]
		else:
			c += [b[f+1]-b[0], b[j]-b[f+1]]

	l = bisect(b, b[j]+((b[n]-b[j])/2))
	l -= 1
	
	if l == j or j == n-2:
		c += [b[j+1]-b[j], b[n]-b[j+1]]
	elif l == n-1:
		c += [b[n-1]-b[j], b[n]-b[n-1]]
	else:
		if abs(b[l]-b[j] - (b[n]-b[l])) <= abs(b[l+1]-b[j] - (b[n]-b[l+1])):
			c += [b[l]-b[j], b[n]-b[l]]
		else:
			c += [b[l+1]-b[j], b[n]-b[l+1]]

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

print(ans)

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

sumai = []
s = 0
for i in ai:
    s += i
    sumai.append(s)
lcut = 0 
rcut = 2 
l1 = sumai[lcut]
r2 = sumai[N-1]-sumai[rcut]
ans = []
for i in range(1,N-2):
    while abs(sumai[lcut]-(sumai[i]-sumai[lcut]))>abs(sumai[lcut+1]-(sumai[i]-sumai[lcut+1])):
        lcut += 1
    while abs((sumai[N-1]-sumai[rcut])-(sumai[rcut]-sumai[i]))>abs((sumai[N-1]-sumai[rcut+1])-(sumai[rcut+1]-sumai[i])):
        rcut += 1
    ans.append(max(sumai[lcut],sumai[i]-sumai[lcut],sumai[N-1]-sumai[rcut],sumai[rcut]-sumai[i])-min(sumai[lcut],sumai[i]-sumai[lcut],sumai[N-1]-sumai[rcut],sumai[rcut]-sumai[i]))
print(min(ans))

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

ans = float('inf')
iB, iD = 1, 3
(P, Q, R), S = As[:3], sum(As[3:])


for iC in range(2, N - 1):
    while P < Q and As[iB] <= Q - P:
        P += As[iB]
        Q -= As[iB]
        iB += 1

    while R < S and As[iD] <= S - R:
        R += As[iD]
        S -= As[iD]
        iD += 1

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

    Q += As[iC]
    R -= As[iC]

print(ans)

Solution (Python):
import bisect

n = int(input())
list = list(map(int, input().split()))
sum = [0] * (n + 1)
for i in range(1, n+1):
    sum[i] = sum[i-1] + list[i-1]
result = []
for i in range(3, n):
    half1 = sum[i-1] // 2
    i1 = bisect.bisect_right(sum, half1)
    if (half1 - sum[i1 - 1]) < sum[i1] - half1:
        a1 = sum[i1 - 1]
        a2 = sum[i-1] - sum[i1 - 1]
    else:
        a1 = sum[i1]
        a2 = sum[i-1] - sum[i1]
    
    
    half2 = (sum[n] + sum[i-1]) // 2
    i2 = bisect.bisect_right(sum, half2)
    if (half2 - sum[i2 - 1]) < sum[i2] - half2:
        a3 = sum[i2 - 1] - sum[i-1]
        a4 = sum[n] - sum[i2 - 1]
    else:
        a3 = sum[i2] - sum[i-1]
        a4 = sum[n] - sum[i2]
    result.append(max(a1,a2,a3,a4) - min(a1,a2,a3,a4))
print(min(result))

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

l = 1
m = 1
r = 3

sumll = a[0]
suml = a[0]
sumrr = sum(a[3:])
sumr = a[1]+a[2]+sumrr

res = sumr + a[0]

for m in range(1,n-2):
    suml += a[m]
    sumr -= a[m]
    while sumll+a[l]<=suml/2 and l<m:
        sumll += a[l]
        l += 1
    while sumrr-a[r]>=sumr/2 and r<n-1:
        sumrr -= a[r]
        r += 1
    p1 = sumll
    q1 = suml - sumll
    r1 = sumr - sumrr
    s1 = sumrr
    
    p2 = p1 + a[l]
    q2 = q1 - a[l]
    r2 = r1 + a[r]
    s2 = s1 - a[r]
    abs1 = max(p1,q1,r1,s1)-min(p1,q1,r1,s1)
    abs2 = max(p2,q2,r2,s2)-min(p2,q2,r2,s2)
    abs3 = max(p1,q1,r2,s2)-min(p1,q1,r2,s2)
    abs4 = max(p2,q2,r1,s1)-min(p2,q2,r1,s1)
    rest = min(abs1,abs2,abs3,abs4)
    if res > rest:
        res = rest

print(res)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
B=A[::-1]
T=[0 for i in range(N+1)]
for i in range(N):
    T[i+1]=T[i]+B[i]
F=[0 for i in range(N)]
G=[0 for i in range(N)]
for i in range(N):
    LS=S[i+1]
    k=0
    if i!=0:
        k=F[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=S[j]
        R=LS-S[j]
        if abs(R-L)<=tmp:
            F[i]=j
        else:
            break
        tmp=abs(R-L)
    if F[i]<=0:
        F[i]=0
for i in range(N):
    RS=T[i+1]
    k=0
    if i!=0:
        k=G[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=T[j]
        R=RS-T[j]
        if abs(R-L)<=tmp:
            G[i]=j
        else:
            break
        tmp=abs(R-L)
    if G[i]<=0:
        G[i]=0
ans=S[N]
for i in range(N):
    A=[0 for i in range(4)]
    k=0
    if i!=0:
        k=F[i-1]
    A[0]=S[k]
    A[1]=S[i]-S[k]
    A[2]=T[N-i]-T[G[N-i-1]]
    A[3]=T[G[N-i-1]]
    score=max(A)-min(A)
    if ans>score:
        ans=score
print(ans)

Solution (Python):
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]



As = list(accumulate(As))


def bsearch(L, l, r, ls, rs):
    if r - l == 0:
        l_temp = L[l-1] if l!=0 else 0
        lsum = l_temp - ls
        return [max(lsum, rs - L[l]), min(lsum, rs - L[l]) + L[l] - l_temp]
    n = int((r-l)/2)
    lsum = L[l+n] - ls
    rsum = rs - L[l+n]
    if lsum > rsum:
        return bsearch(L, l, l+n, ls, rs)
    else:
        return bsearch(L, l+n+1, r, ls, rs)

for i in range(N-3):
    cs = bsearch(As, 0, i+1, 0, As[i+1]) + bsearch(As ,i+2, N-1, As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)

Solution (Python):
import bisect
N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
total = accum[N]


ans = float('inf')
for i in range(2, N - 1, 1): 
    zenhan = accum[i] 
    kouhan = total - zenhan 
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], zenhan - accum[index1], accum[index3] - zenhan, total - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)

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

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = list(accumulate(A))
    l = 0
    r = 0
    for i in range(1, N - 2):
        while cs[i] > cs[l] + cs[l+1]:
            l += 1
        while cs[-1] + cs[i] > cs[r] + cs[r+1]:
            r += 1
        P = cs[l]
        Q = cs[i] - P
        R = cs[r] - P - Q
        S = cs[-1] - cs[r]
        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_left

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

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

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

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

    M = max(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])
    m = min(P[Lx], P[i]-P[Lx], P[Rx]-P[i], P[N]-P[Rx])

    ans = min(ans, M-m)

print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
c=[0 for i in range(n)]


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

l=0
r=2
f=float("inf")
for i in range(1,n-1):
 while abs(c[l]-(c[i]-c[l]))>abs(c[l+1]-(c[i]-c[l+1])):
   l+=1
 while abs(c[r]-c[i]-(c[n-1]-c[r]))>abs(c[r+1]-c[i]-(c[n-1]-c[r+1])):
   r+=1
 e=[c[l],c[i]-c[l],c[r]-c[i],c[n-1]-c[r]]
 f=min(f,max(e)-min(e))
print(f)