Problem:
 Score : 600 points    Problem Statement Snuke has an integer sequence A of length N .  He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E .
The positions of the cuts can be freely chosen.  Let P,Q,R,S be the sums of the elements in B,C,D,E , respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S .      Constraints  4 \leq N \leq 2 \times 10^5  1 \leq A_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S .        Sample Input 1 5
3 2 4 1 2      Sample Output 1 2  If we divide A as B,C,D,E=(3),(2),(4),(1,2) , then P=3,Q=2,R=4,S=1+2=3 .
Here, the maximum and the minimum among P,Q,R,S are 4 and 2 , with the absolute difference of 2 .
We cannot make the absolute difference of the maximum and the minimum less than 2 , so the answer is 2 .       Sample Input 2 10
10 71 84 33 6 47 23 25 52 64      Sample Output 2 36       Sample Input 3 7
1 2 3 1000000000 4 5 6      Sample Output 3 999999994

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ans = 10**19
sum_a = [0]
for x in a:
    sum_a.append(sum_a[-1]+x)

for q_r in range(2,n-1):
    pq = sum_a[q_r]
    rs = sum_a[n]-sum_a[q_r]
    
    ok1 = 1
    ng1 = q_r
    while ng1-ok1 > 1:
        mid1 = (ng1+ok1)//2
        if pq > 2*sum_a[mid1]:
            ok1 = mid1
        else:
            ng1 = mid1
    p1 = sum_a[ok1]
    q1 = pq-p1
    p2 = sum_a[ok1+1]
    q2 = pq-p2
    if abs(p1-q1) > abs(p2-q2):
        p = p2
        q = q2
    else:
        p = p1
        q = q1
    ok2 = q_r+1
    ng2 = n
    while ng2-ok2>1:
        mid2 = (ng2+ok2)//2
        if rs > 2*(sum_a[mid2]-pq):
            ok2 = mid2
        else:
            ng2 = mid2
    r1 = sum_a[ok2]-pq
    s1 = rs-r1
    r2= sum_a[ok2+1]-pq
    s2 = rs-r2
    if abs(r1-s1) > abs(r2-s2):
        r = r2
        s = s2
    else:
        r = r1
        s = s1
    
    ans = min(ans,max(p,q,r,s)-min(p,q,r,s))

print(ans)

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

def calc(B):
    P, Q = B[0], B[1]
    ret = [None] * N
    ret[1] = (P, Q)
    mid = 1

    for right in range(2, N - 2):
        Q += B[right]
        while mid < right:
            newP = P + B[mid]
            newQ = Q - B[mid]

            if abs(newP - newQ) >= abs(P - Q):
                break
            mid += 1
            P = newP
            Q = newQ

        ret[right] = (P, Q)

    return ret

left = calc(A)[1: -2]
right = calc(A[:: -1])[1: -2][:: -1]

ans = 10**10
for (P, Q), (R, S) in zip(left, right):
    ans = min(ans, abs(max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

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

N = int(input())
A = list(map(int, input().split()))
S = [0]
for a in A:
    S += [S[-1] + a]

ans = float("inf")
l = 0
r = 2
for i in range(1, N - 1):
    while S[l] < S[i] - S[l + 1]:
        l += 1
    while S[r] - S[i] < S[N] - S[r + 1]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]

    ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)

Solution (Python):
import bisect

def cumsum(inlist):
    s = 0
    outlist = [0]
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

def bis(inlist, l, r):
    ok = r
    ng = l
    while ok - ng > 1:
        mid = (ok+ng)//2
        if inlist[r] - 2*inlist[mid] + inlist[l] > 0:
            ng = mid
        else:
            ok = mid
    upper = inlist[r] - 2*inlist[ok] + inlist[l]
    lower = inlist[r] - 2*inlist[ng] + inlist[l]
    if abs(upper) > abs(lower):
        return inlist[r] - inlist[ng], inlist[ng] - inlist[l]
    else:
        return inlist[r] - inlist[ok], inlist[ok] - inlist[l]



n = int(input())
num = [ int(v) for v in input().split() ]
accum_num = cumsum(num)
ans_list = []

for i in range(2,n+1-2):
    a, b = bis(accum_num, 0, i)
    c, d = bis(accum_num, i, n)
    ans_list2 = sorted([a, b, c, d])
    ans_list.append(ans_list2[-1] - ans_list2[0])
print(min(ans_list))

Solution (Python):
n=int(input())
a=[0]+list(map(int,input().split()))
inf=float("inf")

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

left=1
right=0
ans=inf
for mid in range(2,n-1):
    right=max(right,mid+1)
    while a[left]<a[mid]-a[left]:
        left+=1
    data_1=[[a[left-1],a[mid]-a[left-1]],[a[mid]-a[left],a[left]]]
    while a[right]-a[mid]<a[n]-a[right]:
        right+=1
    data_2=[[a[right-1]-a[mid],a[n]-a[right-1]],[a[n]-a[right],a[right]-a[mid]]]

    for x,y in data_1:
        for z,w in data_2:
            ans=min(ans,max(y,w)-min(x,z))

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
l=0
r=2
ans=10**18
for i in range(1,n-2):
    while b[i]-b[l]>b[l+1]:
        l+=1
    while b[-1]-b[r]>b[1+r]-b[i]:
        r+=1
    p=b[l]
    q=b[i]-b[l]
    rr=b[r]-b[i]
    s=b[n-1]-b[r]
    ans=min(ans,abs(max(p,q,rr,s)-min(p,q,rr,s)))
    
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=[0]+list(accumulate(a))
l=0
r=2
ans=10**18
for i in range(1,n-1):
    while b[i]-b[l]>b[l+1]:
        l+=1
    while b[-1]-b[r]>b[1+r]-b[i]:
        r+=1
    p=b[l]
    q=b[i]-b[l]
    rr=b[r]-b[i]
    s=b[n]-b[r]
    ans=min(ans,abs(max(p,q,rr,s)-min(p,q,rr,s)))
    
print(ans)

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

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 2*10**14
l = 0
temp = 2*10**14
r = 2




        
for i in range(2, N-1):
    r = max(r, i)
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r+1 < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)

Solution (Python):
import bisect
INF = 10**16
n=int(input())
a=list(map(int,input().split()))
la=[0]
for i in range(n):
    la.append(la[i]+a[i])
la.pop(0)
sa = la[-1]
l=0
r=2
res = INF
for i in range(1,n-2):
    while abs(la[l+1]-(la[i]-la[l+1])) < abs(la[l]-(la[i]-la[l])):
        l += 1

    if r == i:
        r += 1
    while abs((la[r+1] - la[i])-(sa - la[r+1])) < abs((la[r] - la[i])-(sa - la[r])):
        r += 1
    r1 = la[l]
    r2 = la[i] - la[l]
    r3 = la[r] - la[i]
    r4 = sa    - la[r]
    res=min(res,max(r1,r2,r3,r4)-min(r1,r2,r3,r4))
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from bisect import bisect_left as bisect
    n=int(input())
    A=list(map(int,input().split()))
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]

    ans=INF
    for j in range(1,n):
        i=bisect(S,S[j]/2)
        k=bisect(S,(S[j]+S[-1])/2)
        ans=min(ans,max(S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k])-min(S[i],S[j]-S[i],S[k]-S[j],S[-1]-S[k]))
        ans=min(ans,max(S[i],S[j]-S[i],S[k-1]-S[j],S[-1]-S[k-1])-min(S[i],S[j]-S[i],S[k-1]-S[j],S[-1]-S[k-1]))
        ans=min(ans,max(S[i-1],S[j]-S[i-1],S[k]-S[j],S[-1]-S[k])-min(S[i-1],S[j]-S[i-1],S[k]-S[j],S[-1]-S[k]))
        ans=min(ans,max(S[i-1],S[j]-S[i-1],S[k-1]-S[j],S[-1]-S[k-1])-min(S[i-1],S[j]-S[i-1],S[k-1]-S[j],S[-1]-S[k-1]))
    print(ans)
resolve()

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

def main():
    N, *A = map(int, open(0).read().split())

    A = [0] + list(accumulate(A))

    ans = float("inf")
    for i in range(2, N - 1):
        lm = A[i] // 2
        l = bisect_left(A, lm)
        if abs(A[l - 1] - lm) < abs(A[l] - lm):
            l -= 1

        rm = (A[i] + A[N]) // 2
        r = bisect_left(A, rm)
        if abs(A[r - 1] - rm) < abs(A[r] - rm):
            r -= 1

        P = A[l]
        Q = A[i] - A[l]
        R = A[r] - A[i]
        S = A[N] - A[r]

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

    print(ans)

main()

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

N, *A = map(int, open(0).read().split())

A = [0] + list(accumulate(A))

ans = float("inf")
for i in range(2, N - 1):
    lm = A[i] // 2
    l = bisect_left(A, lm)
    if abs(A[l - 1] - lm) < abs(A[l] - lm):
        l -= 1

    rm = (A[i] + A[N]) // 2
    r = bisect_left(A, rm)
    if abs(A[r - 1] - rm) < abs(A[r] - rm):
        r -= 1

    P = A[l]
    Q = A[i] - A[l]
    R = A[r] - A[i]
    S = A[N] - A[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()))
s = list(accumulate(a))

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)
print(ans)

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

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

ans = float("inf")

for j in range(2,n-1):
    i_list = []
    i_left = bisect_left(s, s[j-1]//2)-1
    if i_left != -1:
        i_list.append([s[i_left], s[j-1]-s[i_left]])
    if i_left != j-2:
        i_list.append([s[i_left+1], s[j-1]-s[i_left+1]])

    k_list = []
    k_left = bisect_left(s, s[j-1]+(s[-1]-s[j-1])//2)-1
    if k_left != j-1:
        k_list.append([s[k_left] - s[j-1], s[-1]-s[k_left]])
    if k_left != n-2:
        k_list.append([s[k_left+1] - s[j-1], s[-1]-s[k_left+1]])
    for i in i_list:
        for k in k_list:
            tmp = max(i+k)-min(i+k)
            ans = min(ans, tmp)
print(ans)

Solution (Python):
from bisect import bisect_right as br
N = int(input())
A = [int(a) for a in input().split()]
s = sum(A)
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]

mi = 1<<100
for i in range(1, N-1):
    sl = S[i]
    sr = s - sl
    a = br(S, sl//2)
    b = br(S, sl + sr//2)
    L = [S[a], S[i]-S[a], S[b]-S[i], s-S[b]]
    mi = min(mi, max(L) - min(L))
    L = [S[a], S[i]-S[a], S[b-1]-S[i], s-S[b-1]]
    mi = min(mi, max(L) - min(L))
    if a-1 >= 0:
        L = [S[a-1], S[i]-S[a-1], S[b]-S[i], s-S[b]]
        mi = min(mi, max(L) - min(L))
        L = [S[a-1], S[i]-S[a-1], S[b-1]-S[i], s-S[b-1]]
        mi = min(mi, max(L) - min(L))

print(mi)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
AA=[A[0]]
for i in range(1,n):
  AA.append(AA[-1]+A[i])
tot=AA[-1]
import bisect
ans=float("inf")
for i in range(1,n-2):
  cur=AA[i]
  l=bisect.bisect_left(AA,cur//2)
  if l==0:
    L1=[0,float("inf")]
  else:
    L1=[AA[l-1],cur-AA[l-1]]
  L2=[AA[l],cur-AA[l]]
  
  r=bisect.bisect_left(AA,cur+(tot-cur)//2)
  if r-1==i:
    R1=[0,float("inf")]
  else:
    R1=[AA[r-1]-cur,tot-AA[r-1]]
  R2=[AA[r]-cur,tot-AA[r]]
  A11=L1+R1
  A12=L1+R2
  A21=L2+R1
  A22=L2+R2
  a11=max(A11)-min(A11)
  a12=max(A12)-min(A12)
  a21=max(A21)-min(A21)
  a22=max(A22)-min(A22)

  ans=min(ans,a11,a12,a21,a22)
print(ans)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
AA=[A[0]]
for i in range(1,n):
  AA.append(AA[-1]+A[i])
tot=AA[-1]
import bisect
ans=float("inf")
for i in range(1,n-2):
  cur=AA[i]
  l=bisect.bisect_left(AA,cur//2)
  if l==0:
    L1=[0,float("inf")]
  else:
    L1=[AA[l-1],cur-AA[l-1]]
  L2=[AA[l],cur-AA[l]]
  
  r=bisect.bisect_left(AA,cur+(tot-cur)//2)
  if r-1==i:
    R1=[0,float("inf")]
  else:
    R1=[AA[r-1]-cur,tot-AA[r-1]]
  R2=[AA[r]-cur,tot-AA[r]]
  A11=L1+R1
  A12=L1+R2
  A21=L2+R1
  A22=L2+R2
  a11=max(A11)-min(A11)
  a12=max(A12)-min(A12)
  a21=max(A21)-min(A21)
  a22=max(A22)-min(A22)

  ans=min(ans,a11,a12,a21,a22)
print(ans)

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


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


j = 1
k = 3

b = a[0]
c = a[1]
d = a[2]
e = asum-b-c-d

ans = asum

for i in range(2,n):
    while abs(b+a[j] -(c-a[j]))<=abs(b-c) and j<i:
        
        b+=a[j]
        c-=a[j]
        j+=1
    while abs(d+a[k] -(e-a[k]))<=abs(d-e) and k<n-1:
        d += a[k]
        e -= a[k]
        k+=1
    
    ans = min(ans, max(b,c,d,e)-min(b,c,d,e))
    c += a[i]
    d -= a[i]
    
print(ans)

Solution (Python):

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(x,y,i):
        p = [a[x],a[i-1]-a[x],b[y],b[-i-1]-b[y]]
        if 0 in p:
            return float("inf")
        return max(p)-min(p)

    n = I()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        a[i+1] += a[i]
    for i in range(n-1)[::-1]:
        b[i] += b[i+1]
    b.sort()
    ans = float("inf")
    for i in range(2,n-1):
        l = a[i-1]
        r = b[-1-i]
        li = bisect.bisect_left(a,l/2)
        ri = bisect.bisect_left(b,r/2)
        for x in range(max(li-1,0),min(li+2,i-1)):
            for y in range(max(ri-1,0),min(ri+2,n-i-1)):
                ans = min(f(x,y,i),ans)
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

Acum = A.cumsum(); S = Acum[-1]
Acum2 = Acum+Acum
I1 = np.searchsorted(Acum2,Acum)
P1 = Acum[I1]; Q1 = Acum-P1
P2 = P1 - A[I1]; Q2 = P1+Q1-P2
P = np.where(np.abs(P1-Q1) > np.abs(P2-Q2),P2,P1); Q = P1+Q1-P

A = A[::-1]
Acum = A.cumsum(); S = Acum[-1]
Acum2 = Acum+Acum
I1 = np.searchsorted(Acum2,Acum)
P1 = Acum[I1]; Q1 = Acum-P1
P2 = P1 - A[I1]; Q2 = P1+Q1-P2
R = np.where(np.abs(P1-Q1) > np.abs(P2-Q2),P2,P1); S = P1+Q1-R

R = R[::-1]; S = S[::-1]

P,Q,R,S = P[:-1],Q[:-1],R[1:],S[1:]

PQRS = np.vstack([P,Q,R,S])

PQRS

score = np.max(PQRS,axis=0) - np.min(PQRS,axis=0)
answer = score.min()
print(answer)

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

S = [0]

for a in A:
    S += [ S[-1] + a ]

l = 0
r = 2
ans = float('inf') 

for i in range(1, N-1):
    while S[i] - S[l+1] > S[l]:
        l += 1

    while S[N] - S[r+1] > S[r] - S[i]:
        r += 1

    a = S[l]
    b = S[i] - S[l]
    c = S[r] - S[i]
    d = S[N] - S[r]
  
    ans = min(ans, max(a,b,c,d) - min(a,b,c,d))
print(ans)

Solution (Python):
from bisect import bisect_left

N = int(input())
A = [int(i) for i in input().split()]

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

ret = float('inf')
for b in range(1, N - 1) :
    a = bisect_left(A, A[b] / 2)
    c = bisect_left(A, A[b] + (s - A[b]) / 2)
    for i in [a - 1, a] :
        for j in [c - 1, c] :
            if not 0 <= i < b < j < N - 1 :
                continue
            cut = [A[i], A[b] - A[i], A[j] - A[b], s - A[j]]
            ret = min(ret, max(cut) - min(cut))
            
print(ret)

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

cumsum_A = []
cumsum = 0
for a in A:
    cumsum += a
    cumsum_A.append(cumsum)

ans = float('INF')
left = 0
right = 2

for center in range(1, n-2):
    ll_value = cumsum_A[left]
    lc_value = cumsum_A[center] - ll_value
    cr_value = cumsum_A[right] - cumsum_A[center]
    rr_value = cumsum_A[-1] - cumsum_A[right]

    while abs(ll_value - lc_value) > abs(ll_value - lc_value + 2*A[left+1]):
        if left == center - 1:
            break
        left += 1
        ll_value += A[left]
        lc_value -= A[left]

    while abs(cr_value - rr_value) > abs(cr_value - rr_value + 2 * A[right + 1]):
        if right == n - 2:
            break
        right += 1
        cr_value += A[right]
        rr_value -= A[right]

    candidate = max(ll_value, lc_value, cr_value, rr_value) - min(ll_value, lc_value, cr_value, rr_value)
    ans = min(ans, candidate)

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    if n % 2:
        print(2 * n)
    else:
        print(n)
    return


def B():
    n = II()
    a = LI()
    a.sort()
    print(a[n-1]-a[0])
    return


def C():
    return







def D():
    n = II()
    a = LI()
    for i in range(n - 1):
        a[i + 1] += a[i]
    l, r = 0, 0
    ans = inf
    for center in range(1, n - 2):
        r = max(r, center + 1)
        while center - l > 1:
            if abs(a[center] - 2 * a[l]) > abs(a[center] - 2 * a[l + 1]):
                l += 1
            else:
                break
        while n - 1 - r > 1:
            if abs(a[n - 1] - a[r] - (a[r] - a[center])) > abs(a[n - 1] - a[r + 1] - (a[r + 1] - a[center])):
                r += 1
            else:
                break
        b = a[l]
        c = a[center] - a[l]
        d = a[r] - a[center]
        e = a[n - 1] - a[r]
        ans = min(ans, max(b, c, d, e) - min(b, c, d, e))
    print(ans)

        
    return


if __name__ == '__main__':
    D()

Solution (Python):


n = int(input())
a = list(map(int,input().split()))
b = [a[0]]
for i in range(1,n):
  b.append(b[-1] + a[i])
c = []
for i in range(n):
  c.append([abs(b[i] - b[-1]/2),i])
h = -1
j = min(c,key= lambda x:x[0])[1]
p = 0
q = 0
r = b[j]
s = b[-1] - r

can = []
for i in range(n-2):
  q += a[i]
  while True:
    pnew = p + a[h+1]
    qnew = q - a[h+1]
    if abs(pnew-qnew) < abs(p-q):
      h += 1
      p = pnew
      q = qnew
    else:
      break
  r -= a[i]
  while True:
    rnew = r + a[j+1]
    snew = s - a[j+1]
    if abs(rnew-snew) < abs(r-s):
      j += 1
      r = rnew
      s = snew
    else:
      break
  if 1 <= i < n-2:
    can.append(max(p,q,r,s) - min(p,q,r,s))
    

print(min(can))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = list(accumulate(LI() + [0]))
ret = INF
for second_point in range(2, n-1):
    left_sum = L[second_point - 1]
    right_sum = L[-1] - left_sum
    if L[bisect_left(L, left_sum/2)] - left_sum/2 < left_sum/2 - L[bisect_left(L, left_sum/2) - 1] or not bisect_left(L, left_sum/2):
        p = L[bisect_left(L, left_sum/2)]
    else:
        p = L[bisect_left(L, left_sum/2) - 1]
    q = left_sum - p
    if L[bisect_left(L, left_sum + right_sum/2)] - right_sum/2 - left_sum < left_sum + right_sum/2 - L[bisect_left(L, left_sum + right_sum/2) - 1]:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2)]
    else:
        s = L[-1] - L[bisect_left(L, left_sum + right_sum/2) - 1]
    r = right_sum - s
    ret = min(ret, max(p, q, r, s) - min(p, q, r, s))


print(ret)

Solution (Python):

from itertools import accumulate
from bisect import bisect
n = int(input())
a = list(map(int, input().split()))
ans = 10**9
cs = [0] + list(accumulate(a))
for i in range(2, n - 1):
    left = cs[i]
    right = cs[-1] - cs[i]
    lm = bisect(cs, left // 2)
    l1, l2 = cs[lm], left - cs[lm]
    l3, l4 = cs[lm - 1], left - cs[lm - 1]
    if abs(l1 - l2) > abs(l3 - l4):
        l1 = l3
        l2 = l4
    rm = bisect(cs, left + right // 2)
    r1, r2 = cs[rm] - cs[i], right - (cs[rm] - cs[i])
    r3, r4 = cs[rm - 1] - cs[i], right - (cs[rm - 1] - cs[i])
    if abs(r1 - r2) > abs(r3 - r4):
        r1 = r3
        r2 = r4
    ans = min(ans, max(l1, l2, r1, r2) - min(l1, l2, r1, r2))
print(ans)

Solution (Python):
N = int(input())
As = list(map(int,input().split()))
sum_a = [0]
for i in range(N):
  sum_a.append(As[i]+sum_a[i])
ans = float('inf')
p,q = 0,2
for cut in range(2,N-1):
  while p < cut-1:
    if abs(sum_a[cut]-sum_a[p]*2) >= abs(sum_a[cut]-sum_a[p+1]*2):
      p += 1
    else:
      break
      
  while q < N-1:
    if abs(sum_a[N]-sum_a[q]-(sum_a[q]-sum_a[cut])) >= abs(sum_a[N]-sum_a[q+1]-(sum_a[q+1]-sum_a[cut])):
      q += 1
    else:
      break
      
  ls = [sum_a[N]-sum_a[q],sum_a[q]-sum_a[cut],sum_a[cut]-sum_a[p],sum_a[p]]
  ans = min(ans,max(ls)-min(ls))
print(ans)

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

for i in range(N-1):
    a[i+1] += a[i]
j = 0
k = 2
ans = 10**9




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

print(ans)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]

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

j=0
k=2
ans=10**9

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

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

from itertools import accumulate

s = list(accumulate(a))




l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)

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

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

l = 0
r = 2
ans = float("inf")

for m in range(1, n-1):
    while l < m - 1 and abs(s[m] - 2 * s[l]) > abs(s[m] - 2 * s[l+1]):
        l += 1
    while r <= m or r < n - 1 and abs(s[n-1] - 2 * s[r] + s[m]) > abs(s[n-1] - 2 * s[r+1] + s[m]):
        r += 1
    mx = max(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    mn = min(s[l], s[m] - s[l], s[r] - s[m], s[n-1] - s[r])
    ans = min(ans, mx - mn)

print(ans)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))

    l, c, r = 1, 2, 3
    P = sum(al[:l])
    Q = sum(al[l:c])
    R = sum(al[c:r])
    S = sum(al[r:])

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

    while c <= n - 2:
        while True:
            if l == c - 1:
                break
            if abs(P - Q) < abs((P + al[l]) - (Q - al[l])):  
                break

            P += al[l]
            Q -= al[l]
            l += 1

        while True:
            if r == n - 1:
                break
            if abs(R - S) < abs((R + al[r]) - (S - al[r])): 
                break

            R += al[r]
            S -= al[r]
            r += 1

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

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

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))

    l, c, r = 1, 2, 3
    P = sum(al[:l])
    Q = sum(al[l:c])
    R = sum(al[c:r])
    S = sum(al[r:])

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

    while c <= n - 2:
        while True:
            if abs(P - Q) < abs((P + al[l]) - (Q - al[l])):  
                break

            if l == c - 1:
                break

            P += al[l]
            Q -= al[l]
            l += 1

        while True:
            if abs(R - S) < abs((R + al[r]) - (S - al[r])): 
                break
            if r == n - 1:
                break

            R += al[r]
            S -= al[r]
            r += 1

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

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

    print(ans)

if __name__ == '__main__':
    main()

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

N = int(input())
A = [int(s) for s in input().split()]
S = [0] + list(accumulate(A))


def score(i, j, k):
    mx = max(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    mn = min(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    return mx - mn


ans = float("inf")
i = 1
k = 3
for j in range(2, N - 1):
    while i < j - 1 and abs(S[j] - 2 * S[i]) > abs(S[j] - 2 * S[i+1]):
        i += 1
    while k <= j or k < N - 1 and abs(S[N] - 2 * S[k] + S[j]) > abs(S[N] - 2 * S[k+1] + S[j]):
        k += 1
    mx = max(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    mn = min(S[i], S[j] - S[i], S[k] - S[j], S[N] - S[k])
    ans = min(ans, mx - mn)
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline



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

from itertools import accumulate
acc = list(accumulate([0]+a))

j = 1
k = 3
ans = 10**18
for i in range(2,n):
    c = acc[i]//2
    while j < i-1 and acc[j] < c:
        j += 1

    c = (acc[-1]-acc[i])//2
    while k < n-1 and acc[k]-acc[i] < c:
        k += 1

    for jj in range(2):
        for kk in range(2):
            l = (acc[j-jj],acc[i]-acc[j-jj], acc[-1]-acc[k-kk], acc[k-kk]-acc[i])
            res = max(l) - min(l)
            ans = min(ans, res)

    
print(ans)