CodeEff/ECCO huggingface dataset:
# Original solution
from math import ceil
s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
total = 0
for i in range(n):
    a = int(eval(input()))
    w.append(a)
    total += a
mx = max(ceil(total / k), max(w))
while True:
    t = []
    t.append(w[0])
    for i in range(1,len(w)):
        if t[len(t)-1] + w[i] <= mx:
            t[len(t)-1] += w[i]
        else:
            t.append(w[i])
            if len(t) > k:
                break
    if len(t) > k:
        mx += 1
    else:
        break
print(mx)

# Optimized solution
def check(P,w,n):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i

s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
for i in range(n):
    a = int(eval(input()))
    w.append(a)

left = 0
right = 100000 * 10000
while right - left > 1:
    mid = int((right + left) / 2)
    v = check(mid,w,n)
    if v >= n:
        right = mid
    else:
        left = mid
print(right)
# Original solution
n, k = list(map(int, input().split(' ')))
w_s = [int(eval(input())) for i in range(n)]

max_w = max(w_s)

while True:
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > max_w:
            tmp_k += 1
            tmp_total_w = w

    if tmp_k <= k:
        break

    max_w += 1

print(max_w)


# Optimized solution
def calc_k_constP(P):
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > P:
            tmp_k += 1
            tmp_total_w = w

    return tmp_k

n, k = list(map(int, input().split(' ')))
w_s = [int(eval(input())) for i in range(n)]

max_w = max(w_s)

left, right = max_w, 10000 * n
while left < right:
    mid = (right + left) // 2
    tmp_k = calc_k_constP(mid)
    if tmp_k <= k:
        right = mid
    else:
        left = mid + 1

print(left)
# Original solution
def binary_search(n, k, lw):
    left = 0
    right = max(lw) * n

    while left <= right:
        mid = (left + right)//2
        if is_underweight(n, k, lw, p=mid):
            right = mid - 1
        else:
            left = mid + 1

    if is_underweight(n, k, lw, p=right):
        return right
    else:
        return left

def is_underweight(n, k, lw, p):
    i = 0
    w = 0
    ck = 1
    while i < n:
        if lw[i] > p:
            return False
        rest = p - w
        if lw[i] <= rest:
            w += lw[i]
            i += 1
        else:
            w = 0
            ck += 1
    return ck <= k

def main():
    n, k = list(map(int, input().split()))
    lw = []
    for _ in range(n):
        lw.append(int(eval(input())))

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()



# Optimized solution
def binary_search(n, k, lw):
    left = 0
    right = max(lw) * n

    while left < right:
        mid = (left + right)//2
        if is_underweight(n, k, lw, p=mid):
            right = mid
        else:
            left = mid + 1

    return left

def is_underweight(n, k, lw, p):
    i = 0
    w = 0
    ck = 1
    while i < n:
        if lw[i] > p:
            return False
        rest = p - w
        if lw[i] <= rest:
            w += lw[i]
            i += 1
        else:
            w = 0
            ck += 1
    return ck <= k

def main():
    n, k = list(map(int, input().split()))
    lw = []
    for _ in range(n):
        lw.append(int(eval(input())))

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()
# Original solution

def check_alloc(weights, cnt, cpct, st, stn):	
	num = 1
	cur = stn
	for i in range(st, len(weights)):
		w = weights[i]
		if cur + w > cpct:
			if num == 1:
				st = i
				stn = cur
			cur = w
			num += 1
			if num > cnt or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = list(map(int, input().split()))
weights = [0] * n
cpct = 0
for i in range(n):
	weight = int(eval(input()))
	weights[i] = weight
	cpct += weight

cpct = int(cpct/k)
st = 0
stn = 0
while True:
	can_alloc = check_alloc(weights, k, cpct, st, stn)
	if can_alloc == False:
		cpct += 1
	else:
		break

print(cpct)



# Optimized solution
import sys

def check_alloc(weights, cnt, cpct):	
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > cnt or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = list(map(int, input().split()))
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	weight = int(eval(input()))
	weights[i] = weight
	sum += weight
	maxi = max(maxi, weight)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
mid = 0
while start <= end:
	mid = int(start + (end - start) / 2)
	can_alloc = check_alloc(weights, k, mid)
	if can_alloc == False:
		start = mid + 1
	else:
		if start == end: break
		end = mid

print(mid)
# Original solution
def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p_internal(lp, rp, k, ws):
    "?????????P????????????????????¢?´¢??????"
    cp = (lp + rp) // 2
    k1 = calc_k(cp, ws)
    if k1 == k:
        # ???????????¨????????????????°?????????¨???k??°????????????????????????
        return cp
    elif k1 < k:
        # ???????????¨???????????????k??°???????°?????????????????????§????????????????????????????????????
        return search_minimum_p_internal(lp, cp - 1, k, ws)
    else:
        # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
        return search_minimum_p_internal(cp + 1, rp, k, ws)

def search_minimum_p(k, ws):
    """
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    maxp = 10000 * 100000
    minp = max(ws)
    p = search_minimum_p_internal(minp, maxp, k, ws)
    while True:
        k1 = calc_k(p - 1, ws)
        if k1 == k and p > minp:
            p -= 1
        else:
            return p

n, k = list(map(int, input().split()))
ws = []
for i in range(n):
    ws.append(int(eval(input())))

print((search_minimum_p(k, ws)))

# Optimized solution
def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if w > p:
            return None
        elif s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p(k, ws):
    """
    ?????????P????????????????????¢?´¢??????
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    lp = max(ws)
    rp = 10000 * 100000

    while lp <= rp:
        cp = (lp + rp) // 2
        k1 = calc_k(cp, ws)
        if k1 <= k:
            # ???????????¨???????????????k??°??\????????????????????§??????
            k2 = calc_k(cp - 1, ws)
            if k2 == None or k2 > k:
                # cp???k??°???????????????????????????p???????°??????§??????
                return cp
            else:
                # ???????°???????p????????¨??????
                rp = cp - 1
        else:
            # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
            lp = cp + 1

    return None

n, k = list(map(int, input().split()))
ws = []
for i in range(n):
    ws.append(int(eval(input())))

print((search_minimum_p(k, ws)))
# Original solution
n, k = list(map(int, input().split()))
w = [int(eval(input())) for i in range(n)]
l = max(w)
r = sum(w)

while l < r:
    m = (l + r) // 2
    stack = car = 0
    for i in w:
        stack += i
        if stack > m:
            stack = i
            car += 1
    if car < k:
        r = m
    else:
        l = m + 1
print(l)

# Optimized solution
import sys

n, k = list(map(int, input().split()))
w = [int(sys.stdin.readline()[:-1]) for i in range(n)]
l = max(w)
r = sum(w)

while l < r:
    m = (l + r) // 2
    stack = car = 0
    for i in w:
        stack += i
        if stack > m:
            stack = i
            car += 1
    if car < k:
        r = m
    else:
        l = m + 1
print(l)
# Original solution
from math import ceil


def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(eval(input())) for _ in range(n)]

p = max(ceil(sum(ws) / k), *ws)

while True:
    if check_p(p):
        break
    p += 1

print(p)

# Optimized solution
def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(eval(input())) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)
# Original solution
def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(eval(input())) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)

# Optimized solution
def check_p(p):
    global k, ws
    lt, nt = 0, 1  # loadage_of_current_truck, num_of_truck
    for w in ws:
        lt += w
        if lt > p:
            nt += 1
            if nt > k:
                return False
            lt = w
    return True


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

ws = [int(eval(input())) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)
# Original solution
import sys
n, k = list(map(int, input().split()))

ws = list(map(int, sys.stdin.read().split()))
h = sum(ws)
p = h // k


def isEnough(A, n, k, w):
    ps = [w for x in range(k)]
    j = 0
    for i in range(n):
        a = A[i]
        p = ps[j]
        if p < a:
            j += 1
            if j < k:
                p = ps[j]
            else:
                return False
        dif = p - a
        if dif < 0:
            return False
        else:
            ps[j] = dif
    return True

while not isEnough(ws, n, k, p):
    p += 1

print(p)

# Optimized solution
import sys
n, k = list(map(int, input().split()))

ws = list(map(int, sys.stdin.read().split()))
h = sum(ws)
p = h // k


def isEnough(A, n, k, w):
    one = w
    count = 0
    for a in A:
        if one < a:
            count += 1
            if count < k:
                one = w
            else:
                return False
        dif = one - a
        if dif < 0:
            return False
        else:
            one = dif
    return True

while not isEnough(ws, n, k, p):
    p += 1

print(p)
# Original solution
import sys
import math

def check_sekisairyo(k, p_min, w_i):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = list(map(int, input().split()))
w_i = [int(eval(input())) for i in range(n)]
p_min = math.floor(sum(w_i) / k)
w_max = max(w_i)
if p_min < w_max:
    p_min = w_max
while not check_sekisairyo(k, p_min, w_i):
    p_min += 1
print(p_min)

# Optimized solution
import sys

def check_sekisairyo(p_min):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = list(map(int, input().split()))
w_i = [int(eval(input())) for i in range(n)]
left, right, p_min = max(w_i), sum(w_i), 0
while left < right:
    p_min = (left + right) // 2
    if check_sekisairyo(p_min):
        right = p_min
    else:
        left = p_min = p_min + 1
print(p_min)
# Original solution


def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            if count > k :
                return False
            tmpList = []
            tmpList.append(x)
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(eval(input())))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)

# Optimized solution


def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(eval(input())))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
# Original solution
import sys
n, k = list(map(int, input().split()))
w = tuple(map(int, sys.stdin.readlines()))
p = max(w)
s = sum(w)
if n <= k:
    print(p)
elif k == 1:
    print(s)
else:
    a = max(p, s//k)
    while True:
        l = [a]
        for i in range(n):
            d = l[-1] - w[i]
            if d < 0:
                l.append(a-w[i])
            else:
                l[-1] = d
            i += 1
        if len(l) > k:
            a += 1
        else:
            break
    print(a)

# Optimized solution
n,k = list(map(int, input().split()))
w = [int(eval(input())) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
m = l + (s-l)*k//n
while s < l:
    if check(m):
        l = m
    else:
        s = m+1
    m = (s+l)//2
print(m)
# Original solution
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return True

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return False
    pass

# ??\?????¨
n, k = list(map(int, sys.stdin.readline().split()))
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    # print(max_p, min_p)
    # sys.exit(0)

    capable = {min_p:False, max_p:True}

    # sys.exit(0)
    
    bottom = min_p
    top = max_p

    while bottom < top:
        mid = (bottom + top) // 2

        if mid not in capable:
            capable[mid] = is_capable(n, k, w, mid)

        if capable[mid] == True:
            if (mid - 1) not in capable:
                capable[mid - 1] = is_capable(n, k, w, mid - 1)

            if capable[mid - 1] == False:
                ans = mid
                break
            else:
                top = mid
        elif capable[mid] == False:
            if (mid + 1) not in capable:
                capable[mid + 1] = is_capable(n, k, w, mid + 1)

            if capable[mid + 1] == True:
                ans = mid + 1
                break
            else:
                bottom = mid + 1

    print(ans)
    # print(capable)

# Optimized solution
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return i

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return i
    pass

# ??\?????¨
n, k = list(map(int, sys.stdin.readline().split()))
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    # print(max_p, min_p)
    # sys.exit(0)
    
    bottom = min_p
    top = max_p

    while top - bottom > 1:
        mid = (bottom + top) // 2

        if is_capable(n, k, w, mid) == n:
            top = mid
        else:
            bottom = mid

    print(top)
# Original solution
from collections import deque
N=int(eval(input()))
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
K=A[:2]
L=deque(A[2:])
for i in range(2,N-1):
    a=L.popleft()
    L.appendleft(a)
    K.append(a)
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    #print(abs(max(ans)-min(ans)))
    num=min(num,abs(max(ans)-min(ans)))
    L.popleft()
print(num)

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

# Optimized solution
#from collections import deque
from bisect import bisect_left
N=int(eval(input()))
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]

num=10**14
for i in range(2,N-1):
    ans=[]
    x=(A[i]+A[0])/2
    j=bisect_left(A,x)
    #print(j,x)
    if A[j]-x>x-A[j-1]:
        j-=1
    ans+=[A[j]-A[0],A[i]-A[j]]
    y=(A[N]+A[i])/2
    k=bisect_left(A,y)
    #print(k,y)
    if A[k]-y>y-A[k-1]:
        k-=1
    ans+=[A[N]-A[k],A[k]-A[i]]
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)
# Original solution
from itertools import accumulate
from bisect import bisect_right
N = int(eval(input()))
A = list(map(int, input().split()))

# 累積和を前計算
cumsum = list(accumulate(A))
cumsum.insert(0, 0)

#print(cumsum)
ans = float('inf')
# 真ん中を全探索
for i in range(2, N-1):
    #print(A[:i], A[i:])
    # 左の真ん中
    LC = cumsum[i] / 2

    LX = bisect_right(cumsum, LC)
    #print(LX)
    # 超えるべきか超えないべきか
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    # 右の真ん中
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_right(cumsum, RC)
    # 超えるべきか超えないべきか
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

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

print(ans)


# Optimized solution
from itertools import accumulate
from bisect import bisect_right, bisect_left

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

# 累積和を前計算
cumsum = list(accumulate(A))
cumsum.insert(0, 0)  # out of index 対策


ans = float('inf')
# 真ん中を全探索
for i in range(2, N-1):
    #print(cumsum[:i], cumsum[i:])
    # 左の真ん中
    LC = cumsum[i] / 2

    LX = bisect_left(cumsum, LC)
    #print(LX)
    # 超えるべきか超えないべきか
    if abs(cumsum[LX-1] - LC) < abs(cumsum[LX] - LC):
        LX -= 1

    # 右の真ん中
    RC = (cumsum[N] + cumsum[i]) / 2
    RX = bisect_left(cumsum, RC)
    # 超えるべきか超えないべきか
    if abs(cumsum[RX-1] - RC) < abs(cumsum[RX] - RC):
        RX -= 1

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

print(ans)
# Original solution
from bisect import bisect_left
from itertools import accumulate

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

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

ans = float('inf')
# 真ん中区切り全探索
for m in range(2, N-1):
    # 左
    Lmid = cumsum[m] / 2
    Lx = bisect_left(cumsum, Lmid)

    # 境界チェック
    if abs(Lmid - cumsum[Lx]) > abs(Lmid - cumsum[Lx-1]):
        Lx -= 1


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

    # 境界チェック
    if abs(Rmid - cumsum[Rx]) > abs(Rmid - cumsum[Rx-1]):
        Rx -= 1

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

print(ans)


# Optimized solution
from bisect import bisect_left
from itertools import accumulate
N = int(eval(input()))
A = list(map(int, input().split()))

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

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

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

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

print(ans)