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 = input().split()
a = [int(m) for m in a]
asum = []
t = 0
for i in range(n):
    t += a[i]
    asum.append(t)
x1 = 0
x2 = 0
x3 = 0
x4 = 0
s1 = 1
s2 = 3
ansli = []
for i in range(n - 3):
    ansli.append([])
ac = 2
bc = 2
for i in range(2, n - 1):
    for j in range(s1, i):
        if j == 1:
            s1l = asum[0]
            s1r = asum[i - 1] - asum[0]
            cr = abs(s1l - s1r)
            ac = 2
        else:
            if ac == 1:
                s1r += a[i - 1]
                cr = abs(s1l - s1r)

            s1l2 = asum[j - 1]
            s1r2 = asum[i - 1] - asum[j - 1]
            cr2 = abs(s1l2 - s1r2)
            if cr2 <= cr:
                s1l = s1l2
                s1r = s1r2
                cr = cr2
                s1 = j
                ac = 2
            else:
                break
    ansli[i - 2].append(s1l)
    ansli[i - 2].append(s1r)
    ac = 1
    for k in range(s2, n):
        if k == 3:
            s2l = asum[i] - asum[i - 1]
            s2r = asum[n - 1] - asum[i]
            crw = abs(s2l - s2r)
            bc = 2
        else:
            if bc == 1:
                s2l -= a[i - 1]
                crw = abs(s2l - s2r)

            s2l2 = asum[k - 1] - asum[i - 1]
            s2r2 = asum[n - 1] - asum[k - 1]
            cr2w = abs(s2l2 - s2r2)
            if cr2w <= crw:
                s2l = s2l2
                s2r = s2r2
                crw = cr2w
                s2 = k
                bc = 2
            else:
                break
    ansli[i - 2].append(s2l)
    ansli[i - 2].append(s2r)
    bc = 1
ransli = []
for i in range(n - 3):
    p = max(ansli[i])
    q = min(ansli[i])
    ransli.append(p - q)

print(min(ransli))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
T=[]
for i in range(N):
  if i==0:
    T.append(A[i])
  else:
    T.append(T[i-1]+A[i])
ans=float("inf")
x=1
y=1
for i in range(2,N):
  while abs(T[i-1]-2*T[x-1])>abs(T[i-1]-2*T[x]):
    x+=1
  while abs(T[i-1]+T[N-1]-2*T[y-1])>abs(T[i-1]+T[N-1]-2*T[y]):
    y+=1
  P=T[x-1]
  Q=T[i-1]-T[x-1]
  R=T[y-1]-T[i-1]
  S=T[N-1]-T[y-1]
  A=max(P,Q,R,S)
  B=min(P,Q,R,S)
  ans=min(ans,A-B)
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d1 = 1
    d2 = 2
    d3 = 3
    P = A[0]
    Q = A[1]
    R = A[2]
    S = sum(A[3:])
    ans = max(P, Q, R, S) - min(P, Q, R, S)
    while d2 <= N-2:
        while d1 < d2-1:
            x = A[d1]
            if abs((Q-x) - (P+x)) < abs(Q - P):
                P += x
                Q -= x
                d1 += 1
            else:
                break
        while d3 < N-1:
            x = A[d3]
            if d2 >= d3 or abs((S-x) - (R+x)) < abs(S - R):
                R += x
                S -= x
                d3 += 1
            else:
                break
        current = max(P, Q, R, S) - min(P, Q, R, S)
        ans = min(current, ans)
        Q += A[d2]
        R -= A[d2]
        d2 += 1
    print(ans)


if __name__ == "__main__":
    main()

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 True:
        p = cumsum[i]
        q = cumsum[j] - cumsum[i]
        p_new = cumsum[i+1]
        q_new = cumsum[j] - cumsum[i+1]
        if abs(p_new-q_new) < abs(p-q):
            i += 1
        else:
            break

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

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

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

left = 1
right = 3

ans = float('inf')

for mid in range(2, n-1):
    p = a[left - 1]
    q = a[mid - 1] - a[left - 1]
    p_next = a[left]
    q_next = a[mid - 1] - a[left]

    while abs(p_next - q_next) <= abs(p - q):
        left += 1
        p = a[left - 1]
        q = a[mid - 1] - a[left - 1]
        p_next = a[left]
        q_next = a[mid - 1] - a[left]

    r = a[right - 1] - a[mid - 1]
    s = a[n - 1] - a[right - 1]
    r_next = a[right] - a[mid - 1]
    s_next = a[n - 1] - a[right]

    while abs(r_next - s_next) <= abs(r - s):
        right += 1
        r = a[right - 1] - a[mid - 1]
        s = a[n - 1] - a[right - 1]
        r_next = a[right] - a[mid - 1]
        s_next = a[n - 1] - a[right]

    ans = min(ans, abs(min(p, q, r, s) - max(p, q, r, s)))

print(ans)

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

SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)
    
i=1
j=2
k=3
P=SUM[i]
Q=SUM[j]-SUM[i]
R=SUM[k]-SUM[j]
S=SUM[N]-SUM[k]
ANS=10**10
check=1

while j<N-1:
    check=1
    while check==1:
        check=0
        if i<j-1:
            if abs(P-Q)>abs(P+A[i]-Q+A[i]):
                P+=A[i]
                Q-=A[i]
                i+=1
                check=1
        if k<N-1:

            if abs(R-S)>abs(R+A[k]-S+A[k]):
                R+=A[k]
                S-=A[k]
                k+=1
                check=1

    
    
    if ANS>max([P,Q,R,S])-min([P,Q,R,S]):
        ANS=max([P,Q,R,S])-min([P,Q,R,S])

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

print(ANS)

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

accSum = list(accumulate(A))
ans = float('inf')
for m in range(1, N):
    
    Lm = accSum[m] // 2
    Lx = bisect_left(accSum, Lm)
    if abs(accSum[Lx] - Lm) > abs(accSum[Lx - 1] - Lm):
        Lx -= 1

    
    Rm = (accSum[m] + accSum[-1]) // 2
    Rx = bisect_left(accSum, Rm)
    if abs(accSum[Rx] - Rm) > abs(accSum[Rx - 1] - Rm):
        Rx -= 1

    P, Q, R, S = accSum[Lx], accSum[m] - accSum[Lx], accSum[Rx] - accSum[m], accSum[-1] - accSum[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()))
S = [0] * N
S[0] = A[0]
for i in range(1, N):
    S[i] = S[i - 1] + A[i]

num = float("inf")
a = 0
b = 2
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = max(b, i + 1)
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)

Solution (Python):

from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


def left_diff(array):
    """
    array: ordered ndarray, len(array) >= 2
    """
    x = (array[-1] + 1) >> 1
    mid = np.searchsorted(array, x)
    if abs(array[-1] - array[mid] * 2) < abs(array[-1] - array[mid-1] * 2):
        return array[mid], array[-1] - array[mid]
    else:
        return array[mid-1], array[-1] - array[mid-1]


def right_diff(array, offset):
    """
    array: ordered ndarray, len(array) >= 2
        target array or list

    offset: int
        offset value for right array
    """
    x = (array[-1] - offset + 1) >> 1
    mid = np.searchsorted(array, x + offset)
    if abs(array[-1] - array[mid] * 2 + offset)\
            < abs(array[-1] - array[mid-1] * 2 + offset):
        return array[mid] - offset, array[-1] - array[mid]
    else:
        return array[mid-1] - offset, array[-1] - array[mid-1]


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


if __name__ == '__main__':
    N = d_in()
    a_array = np.array(ds_in())

    cum_a = np.cumsum(a_array)
    left_cut_points = (cum_a[1:-2] + 1) // 2
    left_mid_points = np.searchsorted(cum_a, left_cut_points)
    right_cut_points = (cum_a[-1] + cum_a[1:-2] + 1) // 2
    right_mid_points = np.searchsorted(cum_a, right_cut_points)
    
    ans = float('inf')
    for i in range(2):
        for j in range(2):
            P = cum_a[left_mid_points-i]
            Q = cum_a[1:-2] - P
            R = cum_a[right_mid_points-j] - cum_a[1:-2]
            S = cum_a[-1] - cum_a[right_mid_points-j]
            MAX = np.maximum(np.maximum(P, Q), np.maximum(R, S))
            MIN = np.minimum(np.minimum(P, Q), np.minimum(R, S))
            ans = min(ans, (MAX - MIN).min())

    print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
Asum = [0]
for i in range(N):
    Asum.append(Asum[i] + A[i])

left, right = 0, 2
Ans = float("inf")
for i in range(1, N-2):
    B = Asum[left+1]-Asum[0]
    C = Asum[i+1] - Asum[left+1]
    while left < i-1:
        if abs(C-B) > abs(C-B-2*A[left+1]):
            left += 1
            B += A[left]
            C -= A[left]
        else:
            break
    if i == right:
        right = i+1
    D = Asum[right+1] - Asum[i+1]
    E = Asum[N] - Asum[right+1]
    while right < N-2:
        if abs(E-D) > abs(E-D-2*A[right+1]):
            right += 1
            D += A[right]
            E -= A[right]
        else:
            break
    Ans = min(Ans, max(B, C, D, E) - min(B, C, D, E))
print(Ans)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
ruiseki=[0]
for i in range(n):
    ruiseki.append(ruiseki[i] + A[i])

l=1
r=3
ans=[]
for sikiri in range(2,n-1):
    while( ruiseki[sikiri] > 2*ruiseki[l] ):
        l+=1
    if(ruiseki[sikiri] - 2*ruiseki[l-1] <abs(ruiseki[sikiri] - 2*ruiseki[l])):
        l-=1
    r_sum=ruiseki[-1] - ruiseki[sikiri]
    while( r_sum > 2*(ruiseki[r] - ruiseki[sikiri])):
        r+=1
    if( r_sum- 2*(ruiseki[r-1] - ruiseki[sikiri]) <= 2*(ruiseki[r] - ruiseki[sikiri]) - r_sum ):
        r-=1

    if(l<sikiri and sikiri < r):
        tmp=[ruiseki[l],ruiseki[sikiri]-ruiseki[l],ruiseki[r]-ruiseki[sikiri],ruiseki[-1]-ruiseki[r]]
        ans.append(max(tmp) - min(tmp))

print(min(ans))

Solution (Python):
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

Solution (Python):
N = int(input())
H = [int(i) for i in input().split()]
S = [0 for i in range(N)]
S[0] = H[0]
for i in range(1,N):
    S[i] = H[i] + S[i-1]
left = 0
right = 2
D = S[N-1]
for center in range(1,N-2):
    while  abs(S[center]/2-S[left+1]) <= abs(S[center]/2-S[left]) :
        if left+1 == center:
            break
        else:
            left += 1
    if center == right:
        right += 1
    while  abs(S[N-1]+S[center]-2*S[right+1]) <= abs(S[N-1]+S[center]-2*S[right]) :
        if right == N-2:
            break
        else:
            right += 1 
    D = min(
            max(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])-
            min(S[left],S[center]-S[left],S[right]-S[center],S[N-1]-S[right])
            ,D)
print(D)

Solution (Python):
N=int(input())
A = list(map(int,input().split()))
sum_=[A[0]]
ans =float('inf')
for i in range(1,N):
    sum_.append(sum_[i-1]+A[i])

midL=0
midR=2
for i in range(1,N-2):
    minL=float('inf')
    minR=float('inf')
    for j in range(midL,i):
        if abs(sum_[i]-2*sum_[j]) > minL:
            break
        else:
            midL=j
            minL=abs(sum_[i]-2*sum_[j])
        
    for k in range(midR,N-1):
        if abs(sum_[-1]-2*sum_[k]+sum_[i]) > minR:
            break
        else:
            midR=k
            minR=abs(sum_[-1]-2*sum_[k]+sum_[i])
    tmp =  max(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR]) -min(sum_[midL],sum_[i]-sum_[midL],sum_[midR]-sum_[i],sum_[-1]-sum_[midR])
    if ans >tmp:
        ans =tmp
print(ans)

Solution (Python):
import sys
 
n = int(input())
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])
 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)

Solution (Python):
import sys
 
n = int(input())
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])
 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)

Solution (Python):

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

def binsearch(seq, l, r, tar):
    
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)


Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

b1, b3 = (1, 3)
parts = [A[0], A[1], A[2], Asum[N] - Asum[3]]
ans = max(parts) - min(parts)
for b2 in range(2, N - 1):
    parts[1] -= A[b2]
    parts[2] += A[b2]
    if b3 == b2: b3 = b2 + 1
    
    for btmp in range(b1, b2):
        bfr = math.fabs((Asum[b2] - Asum[btmp]) - (Asum[btmp] - Asum[0]))
        aft = math.fabs((Asum[b2] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[0]))
        if aft < bfr: continue
        else: break
    b1 = btmp
    
    for btmp in range(b3, N):
        bfr = math.fabs((Asum[N] - Asum[btmp]) - (Asum[btmp] - Asum[b2]))
        aft = math.fabs((Asum[N] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[b2]))
        if aft < bfr: continue
        else: break
    b3 = btmp
    
    parts = [Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[N] - Asum[b3]]
    if ans > max(parts) - min(parts): ans = max(parts) - min(parts)

print(ans)

Solution (Python):
import sys

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

ans = sys.maxsize

def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))

L = 1
R = 3

for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])

print(ans)

Solution (Python):


INF = float('inf')


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


N = int(input())

A = inpl()
B = A[:]


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

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while B[mid] > B[mid_l] + B[mid_l + 1]:
        mid_l += 1
    while t > B[mid_r] + B[mid_r + 1] - B[mid]:
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)

Solution (Python):


INF = float('inf')


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


N = int(input())

A = inpl()
B = A[:]


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

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

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

print(ans)

Solution (Python):

from itertools import accumulate
_ = int(input())
*a, = accumulate(map(int,input().split()))
l,r,e,ans = 0, 2, a[-1], a[-1]
for m in a[1:-2]:
    
    while a[r] - m < e - a[r+1]:
        r += 1
    
    while a[l] < m - a[l+1]:
        l += 1
    tmp = sorted([ a[l], m-a[l], a[r]-m, e-a[r] ])
    ans = min(ans, tmp[-1]-tmp[0] )
print(ans)

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

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


def c_sum(right, left):
    return C[right] - C[left]


ans = float('inf')
l = 1
r = 2
for m in range(1, N):
    while abs(c_sum(m, l) - c_sum(l, 0)) > abs(c_sum(m, l + 1) - c_sum(l + 1, 0)):
        l += 1

    while abs(c_sum(N, r) - c_sum(r, m)) > abs(c_sum(N, r + 1) - c_sum(r + 1, m)):
        r += 1

    P = c_sum(l, 0)
    Q = c_sum(m, l)
    R = c_sum(r, m)
    S = c_sum(N, r)
    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()))
Asum = [0]
for i in range(N):
  Asum.append(Asum[i] + A[i])
Diff = Asum[N]
m = 0; n = 2
for i in range(N-3):
  flag = True
  P = Asum[m]; Q = Asum[i+2] - Asum[m]
  while flag:
    m += 1
    if abs(Asum[i+2]-Asum[m]*2) < abs(P-Q):
      P = Asum[m]; Q = Asum[i+2] - Asum[m]
    else:
      flag = False
      m -= 1
  flag = True
  R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
  while flag:
    n += 1
    if abs(Asum[N]-Asum[n]*2+Asum[i+2]) < abs(R-S):
      R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
    else:
      flag = False
      n -= 1
  if max(P,Q,R,S)-min(P,Q,R,S) < Diff:
    Diff = max(P,Q,R,S)-min(P,Q,R,S)
print(Diff)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for mid in range(1, len(a)):
  b.append(b[mid - 1] + a[mid])
ans = 10**9


def g_sum(l, r):
  if r < l:
    return 0
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

lef = 1
rit = 2
for mid in range(2, n - 1):
  
  while abs(g_sum(0, lef - 1) - g_sum(lef, mid - 1)) > abs(g_sum(0, lef) - g_sum(lef + 1, mid - 1)):
    lef += 1
  
  while abs(g_sum(mid, rit - 1) - g_sum(rit, n - 1)) > abs(g_sum(mid, rit) - g_sum(rit + 1, n - 1)):
    rit += 1
  
  P = g_sum(0,lef - 1)
  Q = g_sum(lef, mid - 1)
  R = g_sum(mid, rit - 1)
  S = g_sum(rit, n - 1)
  
  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

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

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


def nibutan(l,h):
	if l==0:
		t=(A[h]+1)/2
	else:
		t=(A[h]-A[l]+1)/2+A[l]

	for j in range(30):
		m=(h+l)/2
		if A[m]<t:
			l=m
		else:
			h=m
	if abs(A[h]-t)<abs(t-A[l]):
		return h
	else:
		return l

ans=float("inf")
for i in range(1,N-2): 
	m1=nibutan(0,i)
	x1=A[m1]
	x2=A[i]-A[m1]

	m2=nibutan(i,N-1)
	x3=A[m2]-A[i]
	x4=A[-1]-A[m2]

	x_min=min(x1,x2,x3,x4)
	x_max=max(x1,x2,x3,x4)

	ans=min(ans, x_max-x_min)


print ans

Solution (Python):
from itertools import accumulate

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

cumA = list(accumulate(A))

l_index = 0
r_index = 2
cumA_max = cumA[-1]

diff = cumA_max

for i in range(1, len(A)-2):
  while abs(cumA[i] - cumA[l_index] - cumA[l_index]) > abs(cumA[i] - cumA[l_index + 1] - cumA[l_index + 1]):
    l_index += 1

  while abs(cumA_max - cumA[r_index] - (cumA[r_index] - cumA[i])) > abs(cumA_max - cumA[r_index + 1] - (cumA[r_index + 1] - cumA[i])):
    r_index += 1
        
  left = cumA[l_index]
  center = cumA[i] - cumA[l_index]
  right = cumA[r_index] - cumA[i]
  last = cumA_max - cumA[r_index]

  diff = min(diff, max(left, center, right, last) - min(left, center, right, last))

print(diff)

Solution (Python):
from itertools import accumulate

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

cumA = list(accumulate(A))

l_index = 0
r_index = 2
cumA_max = cumA[-1]

diff = cumA_max

for i in range(1, len(A)-2):
  
  while cumA[l_index] < cumA[i] - cumA[l_index + 1]:
    l_index += 1

  
  while cumA[r_index] - cumA[i] < cumA_max - cumA[r_index + 1]:
    r_index += 1
        
  left = cumA[l_index]
  center = cumA[i] - cumA[l_index]
  right = cumA[r_index] - cumA[i]
  last = cumA_max - cumA[r_index]

  diff = min(diff, max(left, center, right, last) - min(left, center, right, last))

print(diff)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N = int(input())
aa = inpl()
SUM = sum(aa)
SUMaa_L = [0]
SUMaa_R = [SUM]

tmp = 0
for a in aa:
	tmp += a
	SUMaa_L.append(tmp)
	SUMaa_R.append(SUM-tmp)

cutL = []
l = 1
SUML = SUMaa_L[l]
for cutM in range(2,N-1):
	SUM = SUMaa_L[cutM]
	while SUML < SUM/2:
		l += 1
		SUML = SUMaa_L[l]
	l1,l2 = SUMaa_L[l-1], SUMaa_L[l]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutL.append([l2,r2])
	else:
		cutL.append([l1,r1])

cutR = []
r = N-1
SUMR = SUMaa_R[r]
for cutM in reversed(range(2,N-1)):
	SUM = SUMaa_R[cutM]
	while SUMR < SUM/2:
		r -= 1
		SUMR = SUMaa_R[r]
	l1,l2 = SUMaa_R[r+1], SUMaa_R[r]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutR.append([l2,r2])
	else:
		cutR.append([l1,r1])

ans = INF
for i in range(N-3):
	a,b = cutL[i]
	c,d = cutR[N-4-i]
	ans = min(ans,max(a,b,c,d)-min(a,b,c,d))

print(ans)

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


from itertools import accumulate

def getAccumulate(A):
    return list(accumulate(A))

def solve(A):
    accum = getAccumulate(A)
    l_index = 0
    r_index = 2
    accum_max = accum[-1]

    diff = accum_max
    for i in range(1, len(A)-2):
        while accum[i] > accum[l_index] + accum[l_index + 1]:
            l_index += 1
        while accum_max + accum[i] > accum[r_index] + accum[r_index + 1]:
            r_index += 1
        
        left = accum[l_index]
        center = accum[i] - accum[l_index]
        right = accum[r_index] - accum[i]
        last = accum_max - accum[r_index]
        diff = min(diff, max(left, center, right, last) - min(left, center, right, last))
        
    return diff

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(A))

Solution (Python):
from itertools import accumulate

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

sum_a = list(accumulate(A))
lft = 0
rgt = 2
t = sum_a[-1]
ans = t
for i in range(1,N-2):
    while sum_a[i] - sum_a[lft+1] > sum_a[lft]:
        lft += 1

    while t - sum_a[rgt+1] > sum_a[rgt] - sum_a[i]:
        rgt += 1
    p = sum_a[lft]
    q = sum_a[i] - p
    r = sum_a[rgt] - q - p
    s = t - r - q - p

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

lsum=A[0]+A[1] 
rsum=0 
for i in range(2,n):
    rsum+=A[i]

res=lsum+rsum
le=0
ri=2
sum1=0
sum2=lsum
sum3=0
sum4=rsum

for mid in range(2,n-1): 
    while le<mid and (abs((sum1+A[le])-(sum2-A[le]))<abs(sum1-sum2)) :
        sum1+=A[le]
        sum2-=A[le]
        le+=1
    while ri<n and (abs((sum3+A[ri])-(sum4-A[ri]))<abs(sum3-sum4)) :
        sum3+=A[ri]
        sum4-=A[ri]
        ri+=1


    

    res=min(res,max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4))

    sum2+=A[mid]
    sum3-=A[mid]


print(res)

Solution (Python):
from itertools import accumulate

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

sum_a = list(accumulate(A))
lft = 0
rgt = 2
t = sum_a[-1]
ans = t

for i in range(1,N-2):
    
    while sum_a[i] > sum_a[lft] + sum_a[lft+1]:
        lft += 1
        
    while t + sum_a[i] > sum_a[rgt] + sum_a[rgt+1]:
        rgt += 1
        
    p = sum_a[lft]
    q = sum_a[i] - p
    r = sum_a[rgt] - q - p
    s = t - r - q - p
    
    ans = min(ans, max(p,q,r,s) - min(p,q,r,s))
    
print(ans)

Solution (Python):
def getsum(data, start, end):
    if start == 0:
        return data[end - 1]
    else:
        return data[end - 1] - data[start - 1]

def getdiff(data, start_point, second_point, end_point):
    return abs(getsum(data, second_point, end_point) - getsum(data, start_point, second_point))

n = int(input())
input_data = list(map(int,input().split()))
summed_data = []
summed_data.append(input_data[0])

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

first_separator = 1
third_separator = 3
minimized_diff = 2 * pow(10, 5) * pow(10, 9)

for second_separator in range(2, (n - 1)):
    if second_separator >= third_separator:
        third_separator = second_separator + 1

    while first_separator < (second_separator - 1) and getdiff(summed_data, 0, (first_separator + 1), second_separator) < getdiff(summed_data, 0, first_separator, second_separator):
        first_separator = first_separator + 1

    while third_separator < (n - 1) and getdiff(summed_data, second_separator, (third_separator + 1), n) < getdiff(summed_data, second_separator, third_separator, n):
        third_separator = third_separator + 1

    sum_list = [getsum(summed_data, 0, first_separator), getsum(summed_data, first_separator, second_separator), getsum(summed_data, second_separator, third_separator), getsum(summed_data, third_separator, n)]
    diff = max(sum_list) - min(sum_list)
    if diff < minimized_diff:
        minimized_diff = diff

print(minimized_diff)

Solution (Python):
INF = 2 * 10**5 * 10**9
n = int(input())
a = map(int,input().split())
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 1
p2 = 3
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and abs(s[p1] - s[p] + s[p1]) > abs(s[p1+1] - s[p] + s[p1 + 1]):
        p1 += 1
    while p2 < n and abs(s[p2] - s[p]  - s[n] + s[p2]) > abs(s[p2+1] - s[p]  - s[n] + s[p2+1]):
        p2 += 1
    ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
print(ans)

Solution (Python):
INF = 2 * 10**5 * 10**9
n = int(input())
a = map(int,input().split())
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 1
p2 = 3
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and abs(s[p1] - s[p] + s[p1]) > abs(s[p1+1] - s[p] + s[p1 + 1]):
        p1 += 1
    while p2 < n and abs(s[p2] - s[p]  - s[n] + s[p2]) > abs(s[p2+1] - s[p]  - s[n] + s[p2+1]):
        p2 += 1
    ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
print(ans)

Solution (Python):
INF = 2 * 10**5 * 10**9
n = int(input())
a = map(int,input().split())
s = [0]
for x in a:
    s.append(s[-1]+x)
ans = INF
p1 = 1
p = 2
p2 = 3
def update():
    global ans
    if p1 < p and p2 < n:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1],s[p]-s[p1],s[p2]-s[p],s[n]-s[p2]) )
    if p2 < n and p1 - 1 >= 1:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) -  min(s[p1-1],s[p]-s[p1-1],s[p2]-s[p],s[n]-s[p2]) )
    if p1 < p and p2-1 >= p:
        ans = min(ans , max(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1],s[p]-s[p1],s[p2-1]-s[p],s[n]-s[p2-1]) )
    if p1-1 >= 1 and p2-1 >= p:
        ans = min(ans , max(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) -  min(s[p1-1],s[p]-s[p1-1],s[p2-1]-s[p],s[n]-s[p2-1]) ) 
while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
    p2 += 1
update()
while True:
    p += 1
    if p + 1 >= n:
        break
    while p1 < p and s[p1] < s[p] - s[p1]:
        p1 += 1
    while p2 < n and s[p2] - s[p] < s[n] - s[p2]:
        p2 += 1
    update()
print(ans)

Solution (Python):
from itertools import accumulate

N = int(input())
a = list(accumulate([int(i) for i in input().split()]))
l, r = 0, 1
ans = float("inf")
for i in range(1, N-2):
    while abs(a[i] - 2 * a[l+1]) < abs(a[i] - 2 * a[l]) and l < i - 1: l += 1
    while abs(a[-1] - 2 * a[r+1] + a[i]) < abs(a[-1] - 2 * a[r] + a[i]) and r < N - 2: r += 1
    t = [a[l], a[i] - a[l], a[r] - a[i], a[-1] - a[r]]
    ans = min(ans, max(t) - min(t))
print(ans)