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-----
5
3 2 4 1 2

-----Sample Output-----
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.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
tmp = 0
ca = [0]
for ai in a:
	tmp += ai
	ca.append(tmp)
from bisect import bisect_right, bisect_left
ans = float('inf')
(f, g) = (1, 3)
for i in range(2, n - 1):
	while abs(ca[i] - ca[f] - ca[f]) > abs(ca[i] - ca[f + 1] - ca[f + 1]):
		f += 1
	while abs(ca[-1] - ca[g] - (ca[g] - ca[i])) > abs(ca[-1] - ca[g + 1] - (ca[g + 1] - ca[i])):
		g += 1
	l = (ca[f], ca[i] - ca[f], ca[-1] - ca[g], ca[g] - ca[i])
	ans = min(ans, max(l) - min(l))
print(ans)


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)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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

def INT():
	return int(input())

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

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
B = list(accumulate(A))
(l, c, r) = (0, 1, 2)
P = sum(A[:l])
Q = sum(A[l:c])
R = sum(A[c:r])
S = sum(A[r:])
ans = INF
for c in range(1, N - 1):
	while True:
		if abs(P - Q) < abs(P + A[l] - (Q - A[l])):
			break
		if l == c - 1:
			break
		P += A[l]
		Q -= A[l]
		l += 1
	while True:
		if abs(R - S) < abs(R + A[r] - (S - A[r])):
			break
		if r == N - 1:
			break
		R += A[r]
		S -= A[r]
		r += 1
	ans = min(max(P, Q, R, S) - min(P, Q, R, S), ans)
	Q += A[c]
	R -= A[c]
print(ans)


def tmp(a, b, c):
	return (abs(a - b), abs(a - b + 2 * c))

def solve(string):
	(n, *a) = list(map(int, string.split()))
	(l, c, r) = (1, 2, 3)
	(sll, slr, srl, srr) = (sum(a[:l]), sum(a[l:c]), sum(a[c:r]), sum(a[r:]))
	ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
	while c < n - 1:
		(d, dn) = tmp(sll, slr, a[l])
		while dn < d:
			(sll, slr, l) = (sll + a[l], slr - a[l], l + 1)
			(d, dn) = tmp(sll, slr, a[l])
		(d, dn) = tmp(srl, srr, a[r])
		while dn < d:
			(srl, srr, r) = (srl + a[r], srr - a[r], r + 1)
			(d, dn) = tmp(srl, srr, a[r])
		ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
		(slr, srl, c) = (slr + a[c], srl - a[c], c + 1)
	return str(ans)

def __starting_point():
	print(solve('\n'.join([input(), input()])))
__starting_point()


import bisect
n = int(input())
arr = list(map(int, input().split()))
acum = [0]
for i in range(n):
	acum.append(acum[-1] + arr[i])
ans = 10 ** 18
for i in range(2, n - 1):
	suma = acum[i]
	sumb = acum[n] - suma
	posa = bisect.bisect_right(acum, suma // 2)
	diffa = 10 ** 18
	if posa >= 2:
		mina = min(acum[posa - 1], acum[i] - acum[posa - 1])
		maxa = max(acum[posa - 1], acum[i] - acum[posa - 1])
		diffa = maxa - mina
	if posa != i:
		tmina = min(acum[posa], acum[i] - acum[posa])
		tmaxa = max(acum[posa], acum[i] - acum[posa])
		tdiffa = tmaxa - tmina
		if tdiffa < diffa:
			diffa = tdiffa
			mina = tmina
			maxa = tmaxa
	posb = bisect.bisect_right(acum, suma + sumb // 2)
	diffb = 10 ** 18
	if posb >= i + 2:
		minb = min(acum[posb - 1] - acum[i], acum[n] - acum[posb - 1])
		maxb = max(acum[posb - 1] - acum[i], acum[n] - acum[posb - 1])
		diffb = maxb - minb
	if posa != n + 1:
		tminb = min(acum[posb] - acum[i], acum[n] - acum[posb])
		tmaxb = max(acum[posb] - acum[i], acum[n] - acum[posb])
		tdiffb = tmaxb - tminb
		if tdiffb < diffb:
			diffb = tdiffb
			minb = tminb
			maxb = tmaxb
	ans = min(ans, max(maxa, maxb) - min(mina, minb))
print(ans)


def absdiff(a, b):
	return abs(b - a)

def solve(s):
	(n, *a) = list(map(int, s.split()))
	(l, r, ans) = (1, 3, sum(a))
	(sll, slr, srl, srr) = (a[0], 0, sum(a[1:3]), sum(a[3:]))
	for c in range(1, n - 1):
		slr += a[c]
		srl -= a[c]
		r = max(c, r)
		while l < c and absdiff(sll + a[l], slr - a[l]) < absdiff(sll, slr):
			(sll, slr, l) = (sll + a[l], slr - a[l], l + 1)
		while r < len(a) and absdiff(srl + a[r], srr - a[r]) < absdiff(srl, srr):
			(srl, srr, r) = (srl + a[r], srr - a[r], r + 1)
		(_max, _min) = (max(sll, slr, srl, srr), min(sll, slr, srl, srr))
		ans = min(ans, absdiff(_min, _max))
	return ans
print(solve('\n'.join([input(), input()])))


N = int(input())
A = list(map(int, input().split()))
AA = [0] * N
AA[0] = A[0]
for i in range(1, N):
	AA[i] = AA[i - 1] + A[i]
l = 0
r = 2
p = []
for m in range(1, N - 2):
	sl = AA[m]
	sr = AA[N - 1] - sl
	while abs(sl - 2 * AA[l]) > abs(sl - 2 * AA[l + 1]):
		l += 1
	while abs(AA[N - 1] + sl - 2 * AA[r]) > abs(AA[N - 1] + sl - 2 * AA[r + 1]):
		r += 1
	P = AA[l]
	Q = sl - P
	R = AA[r] - sl
	S = sr - R
	ans = max(P, Q, R, S) - min(P, Q, R, S)
	p.append(ans)
print(min(p))


n = int(input())
a = [int(item) for item in input().split()]
cumsum = [0] * n
for i in range(n):
	if i == 0:
		cumsum[0] = a[0]
	else:
		cumsum[i] = cumsum[i - 1] + a[i]
l = 0
r = 2
ans = sum(a)
for i in range(1, n - 1):
	while cumsum[i] - cumsum[l + 1] > cumsum[l]:
		l += 1
	while cumsum[-1] - cumsum[r + 1] > cumsum[r] - cumsum[i]:
		r += 1
	a = cumsum[l]
	b = cumsum[i] - cumsum[l]
	c = cumsum[r] - cumsum[i]
	d = cumsum[-1] - cumsum[r]
	ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)


from itertools import accumulate
from bisect import *
n = int(input())
a = list(map(int, input().split()))
a = [0] + list(accumulate(a))
ans = 10 ** 18
for i in range(2, n):
	b = []
	m = a[i]
	l = bisect_right(a, m / 2)
	if abs(a[l] - m / 2) <= abs(a[l - 1] - m / 2):
		b.append(a[l])
		b.append(m - a[l])
	else:
		b.append(a[l - 1])
		b.append(m - a[l - 1])
	r = bisect_left(a, (a[-1] + m) / 2)
	if abs(a[r] - (a[-1] + m) / 2) <= abs(a[r - 1] - (a[-1] + m) / 2):
		b.append(a[r] - m)
		b.append(a[-1] - a[r])
	else:
		b.append(a[r - 1] - m)
		b.append(a[-1] - a[r - 1])
	ans = min(ans, max(b) - min(b))
print(ans)


from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
ans = 10 ** 18
A = tuple(accumulate(A, initial=0))
i = 1
j = 3
for mid in range(2, N - 1):
	b = A[i] - A[0]
	c = A[mid] - A[i]
	while i + 1 < mid and abs(b - c) > abs(A[mid] + A[0] - 2 * A[i + 1]):
		i += 1
		b = A[i] - A[0]
		c = A[mid] - A[i]
	j = max(j, mid + 1)
	d = A[j] - A[mid]
	e = A[N] - A[j]
	while j + 1 < N and abs(d - e) > abs(A[N] + A[mid] - 2 * A[j + 1]):
		j += 1
		d = A[j] - A[mid]
		e = A[N] - A[j]
	res = max(b, c, d, e) - min(b, c, d, e)
	ans = min(ans, res)
print(ans)


n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
	F[b] = F[b - 1] + A[b]
res = [0] * 4
data = [10 ** 18] * 2
ex = [0] * 4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
	bl = [True, True]
	for j in range(s, i):
		res[0] = F[j]
		res[1] = F[i] - F[j]
		if not bl[0]:
			break
		if data[0] > abs(res[1] - res[0]) or j == s:
			s = j
			ex[0] = res[0]
			ex[1] = res[1]
			data[0] = abs(res[1] - res[0])
		else:
			bl[0] = False
	for k in range(t, n):
		res[2] = F[k] - F[i]
		res[3] = F[n - 1] - F[k]
		if not bl[1]:
			break
		if data[1] > abs(res[3] - res[2]) or k == t:
			t = k
			ex[2] = res[2]
			ex[3] = res[3]
			data[1] = abs(res[3] - res[2])
		else:
			bl[1] = False
	ans = min(ans, max(ex) - min(ex))
print(ans)


import itertools
n = int(input())
lst = list(map(int, input().split()))
lst_accum = list(itertools.accumulate(lst))
min_diff = 10 ** 100
first_cut = 0
third_cut = 2
all_sum = lst_accum[-1]
for k in range(1, len(lst_accum) - 2):
	second_last = lst_accum[k]
	P = lst_accum[first_cut]
	Q = second_last - P
	diff = abs(P - Q)
	while k - first_cut > 1 and diff > abs(second_last - lst_accum[first_cut + 1] * 2):
		first_cut += 1
		P = lst_accum[first_cut]
		Q = second_last - P
		diff = abs(P - Q)
	if third_cut == k:
		third_cut += 1
	third_last = lst_accum[third_cut]
	S = all_sum - third_last
	R = third_last - second_last
	diff = abs(S - R)
	while n - 1 - third_cut > 1 and diff > abs(all_sum - lst_accum[third_cut + 1] * 2 + second_last):
		third_cut += 1
		third_last = lst_accum[third_cut]
		S = all_sum - third_last
		R = third_last - second_last
		diff = abs(S - R)
	min_diff = min(min_diff, max(P, Q, R, S) - min(P, Q, R, S))
print(min_diff)


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)


N = int(input())
A = [int(x) for x in input().split()]
(P, Q, R, S) = (A[0], 0, A[1] + A[2], sum(A[3:]))
(l, r) = (1, 3)
ans = float('inf')
for i in range(2, N - 1):
	Q += A[i - 1]
	while l < i - 1:
		if abs(P - Q) > abs(P + A[l] - (Q - A[l])):
			P += A[l]
			Q -= A[l]
			l += 1
		else:
			break
	R -= A[i - 1]
	if i == r:
		R += A[r]
		S -= A[r]
		r += 1
	while r < N - 1:
		if abs(R - S) > abs(R + A[r] - (S - A[r])):
			R += A[r]
			S -= A[r]
			r += 1
		else:
			break
	ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)


n = int(input())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
	a_cs[i + 1] = a_cs[i] + a[i]
i1 = 1
i3 = 3
ans = 10 ** 14
for i2 in range(2, n - 1):
	while i1 + 1 < i2 and abs(a_cs[i1] * 2 - a_cs[i2]) > abs(a_cs[i1 + 1] * 2 - a_cs[i2]):
		i1 += 1
	while i3 + 1 < n and abs(a_cs[-1] + a_cs[i2] - a_cs[i3] * 2) > abs(a_cs[-1] + a_cs[i2] - a_cs[i3 + 1] * 2):
		i3 += 1
	p = a_cs[i1]
	q = a_cs[i2] - a_cs[i1]
	r = a_cs[i3] - a_cs[i2]
	s = a_cs[n] - a_cs[i3]
	cand = max(p, q, r, s) - min(p, q, r, s)
	ans = min(ans, cand)
print(ans)


N = int(input())
A = list(map(int, input().split()))
s = 0
AS = []
for i in range(N):
	s += A[i]
	AS.append(s)
Ans = AS[N - 1] + 1
L = 0
R = 2
for Mid in range(1, N - 2):
	Sum_L = AS[Mid]
	Sum_R = AS[N - 1] - Sum_L
	while abs(Sum_L - 2 * AS[L]) > abs(Sum_L - 2 * AS[L + 1]):
		L += 1
	while abs(AS[N - 1] - 2 * AS[R] + AS[Mid]) > abs(AS[N - 1] - 2 * AS[R + 1] + AS[Mid]):
		R += 1
	P = AS[L]
	Q = AS[Mid] - AS[L]
	S = AS[R] - AS[Mid]
	T = AS[N - 1] - AS[R]
	Ans = min(Ans, abs(max(P, Q, S, T) - min(P, Q, S, T)))
print(Ans)


import numpy as np
N = int(input())
A = np.zeros(N + 2, dtype=np.int64)
A[1:-1] = input().split()
np.cumsum(A, out=A)
total = A[-1]
A[-1] = 10 ** 18
left = np.searchsorted(A, A / 2)
P1 = A[left - 1]
P2 = A[left]
(Q1, Q2) = (A - P1, A - P2)
np.maximum(P1, Q2, out=P1)
np.minimum(P2, Q1, out=P2)
(P, Q) = (P1, P2)
right = np.searchsorted(A, (total + A) / 2)
R1 = A[right - 1] - A
R2 = A[right] - A
S1 = total - A[right - 1]
S2 = total - A[right]
np.maximum(R1, S2, out=R1)
np.minimum(R2, S1, out=R2)
(R, S) = (R1, R2)
PQRS = np.vstack([P, Q, R, S])
x = np.max(PQRS, axis=0) - np.min(PQRS, axis=0)
answer = x[1:-1].min()
print(answer)


import bisect
n = int(input())
a = list(map(int, input().split()))
cum = [0]
for ai in a:
	cum.append(cum[-1] + ai)
ans = float('inf')
for i in range(2, n - 1):
	bc = cum[i]
	de = cum[-1] - cum[i]
	bc_mid = bc / 2
	de_mid = (cum[i] + cum[-1]) / 2
	i_bc = bisect.bisect_left(cum, bc_mid)
	i_de = bisect.bisect_left(cum, de_mid)
	for cum_b in (cum[i_bc - 1], cum[i_bc]):
		for cum_d in (cum[i_de - 1], cum[i_de]):
			b = cum_b
			c = bc - b
			d = cum_d - bc
			e = de - d
			bcde = [b, c, d, e]
			bcde.sort()
			ans = min(ans, bcde[-1] - bcde[0])
print(ans)


from itertools import accumulate

def solve(string):
	(n, *a) = list(map(int, string.split()))
	(*a,) = accumulate(a)
	(l, c, r) = (0, 1, 2)
	(sll, slr, srl, srr) = (a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r])
	ans = max(sll, slr, srl, srr) - min(sll, slr, srl, srr)
	while c < n - 1:
		while abs(a[c] - 2 * a[l + 1]) < abs(a[c] - 2 * a[l]):
			l += 1
		while abs(a[-1] + a[c] - 2 * a[r + 1]) < abs(a[-1] + a[c] - 2 * a[r]):
			r += 1
		(sll, slr, srl, srr) = (a[l], a[c] - a[l], a[r] - a[c], a[-1] - a[r])
		ans = min(ans, max(sll, slr, srl, srr) - min(sll, slr, srl, srr))
		c += 1
	return str(ans)

def __starting_point():
	print(solve('\n'.join([input(), input()])))
__starting_point()


import itertools
n = int(input())
A = [int(i) for i in input().split()]
A_sum = [0] + list(itertools.accumulate(A))
ans = 10 ** 9
(P, Q, R, S) = (0, 0, 0, 0)
l = 0
r = 2
for i in range(1, n):
	while l < i and abs(A_sum[l] - (A_sum[i] - A_sum[l])) >= abs(A_sum[l + 1] - (A_sum[i] - A_sum[l + 1])):
		l += 1
	while r < n and abs(A_sum[n] - A_sum[r] - (A_sum[r] - A_sum[i])) >= abs(A_sum[n] - A_sum[r + 1] - (A_sum[r + 1] - A_sum[i])):
		r += 1
	P = A_sum[l]
	Q = A_sum[i] - P
	R = A_sum[r] - A_sum[i]
	S = A_sum[n] - A_sum[r]
	ans = min(ans, abs(max(P, Q, R, S) - min(P, Q, R, S)))
print(ans)


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)


N = int(input())
A = list(map(int, input().split()))
B = [0]
tmp = 0
for a in A:
	tmp += a
	B.append(tmp)
l = 1
r = 3
cut = []
for i in range(2, N - 1):
	Lm = float('inf')
	Rm = float('inf')
	c = [0, i, 0]
	for j in range(l, i):
		tmp = abs(B[i] - 2 * B[j])
		if tmp > Lm:
			c[0] = j - 1
			l = j - 1
			break
		Lm = tmp
	else:
		c[0] = i - 1
		l = i - 1
	for k in range(r, N):
		tmp = abs(B[N] - B[k] - (B[k] - B[i]))
		if tmp > Rm:
			c[2] = k - 1
			r = k - 1
			break
		Rm = tmp
	else:
		c[2] = N - 1
		r = N
	cut.append(c)
ans = float('inf')
for (p, q, r) in cut:
	P = B[p]
	Q = B[q] - B[p]
	R = B[r] - B[q]
	S = B[N] - B[r]
	ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)


N = int(input())
A = [0] * N
S = 0
for (i, a) in enumerate(input().split()):
	S += int(a)
	A[i] = S
answer = S
B = 0
D = 0
for C in range(1, N - 2):
	D = max(D, C + 1)
	SB = A[B]
	SC = A[C] - A[B]
	SD = A[D] - A[C]
	SE = S - A[D]
	left_score = abs(SB - SC)
	while True:
		B_ = B + 1
		SB_ = A[B_]
		SC_ = A[C] - SB_
		x = abs(SB_ - SC_)
		if left_score > x:
			(B, SB, SC, left_score) = (B_, SB_, SC_, x)
			continue
		break
	right_score = abs(SE - SD)
	while True:
		D_ = D + 1
		SD_ = A[D_] - A[C]
		SE_ = S - A[D_]
		x = abs(SD_ - SE_)
		if right_score > x:
			(D, SD, SE, right_score) = (D_, SD_, SE_, x)
			continue
		break
	score = max(SB, SC, SD, SE) - min(SB, SC, SD, SE)
	answer = min(score, answer)
print(answer)


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]
leftMiddle = 0
rightMiddle = 2
ans = float('inf')
for middle in range(2, N - 1):
	leftS = S[leftMiddle]
	rightS = S[middle] - leftS
	diff = abs(leftS - rightS)
	for i in range(leftMiddle, middle):
		leftS += A[i]
		rightS -= A[i]
		if diff > abs(leftS - rightS):
			leftMiddle += 1
			diff = abs(leftS - rightS)
		else:
			break
	leftS = S[rightMiddle] - S[middle]
	rightS = S[-1] - S[rightMiddle]
	diff = abs(leftS - rightS)
	for i in range(rightMiddle, N):
		leftS += A[i]
		rightS -= A[i]
		if diff > abs(leftS - rightS):
			rightMiddle += 1
			diff = abs(leftS - rightS)
		else:
			break
	B = S[leftMiddle]
	C = S[middle] - B
	D = S[rightMiddle] - S[middle]
	E = S[-1] - B - C - D
	diff = max(B, C, D, E) - min(B, C, D, E)
	ans = min(ans, diff)
print(ans)


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)


from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
	tmp = 0
	for i in range(N):
		tmp += abs(a[i] - a[n - 1])
	return tmp
N = int(input())
a = list(map(int, input().split()))
a = list(acc(a))
ans = 10 ** 18
p = 0
q = 2
for j in range(1, N - 2):
	q = max(q, j + 1)
	while p < j - 1 and abs(a[j] - a[p] * 2) > abs(a[j] - a[p + 1] * 2):
		p += 1
	while q < N - 2 and abs(a[j] + a[N - 1] - a[q] * 2) > abs(a[j] + a[N - 1] - a[q + 1] * 2):
		q += 1
	(P, Q, R, S) = (a[p], a[j] - a[p], a[q] - a[j], a[N - 1] - a[q])
	ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
	a[i + 1] += a[i]
l = 0
r = 2
ans = float('inf')
for m in range(1, n - 1):
	while abs(2 * a[l] - a[m]) > abs(2 * a[l + 1] - a[m]):
		l += 1
	while abs(2 * a[r] - a[n - 1] - a[m]) > abs(2 * a[r + 1] - a[n - 1] - a[m]):
		r += 1
	bcde = [a[l], a[m] - a[l], a[r] - a[m], a[n - 1] - a[r]]
	ans = min(ans, max(bcde) - min(bcde))
print(ans)


N = int(input())
alist = list(map(int, input().split()))
slist = []
asum = 0
for a in alist:
	asum += a
	slist.append(asum)
(dic_lp, dic_rp) = ({}, {})
(lp, rp) = (0, 2)
for mp in range(1, N - 2):
	mindiff = slist[mp]
	while lp < mp + 1:
		sum1 = slist[lp]
		sum2 = slist[mp] - slist[lp]
		diff = abs(sum1 - sum2)
		if mindiff > diff:
			lp += 1
			mindiff = diff
		else:
			lp -= 1
			dic_lp[mp] = lp
			break
	rp = max(rp, mp + 1)
	mindiff = slist[-1] - slist[mp]
	while rp < N:
		sum1 = slist[-1] - slist[rp]
		sum2 = slist[rp] - slist[mp]
		diff = abs(sum1 - sum2)
		if mindiff > diff:
			rp += 1
			mindiff = diff
		else:
			rp -= 1
			dic_rp[mp] = rp
			break
min_diff = 10 ** 9
for mp in range(1, N - 2):
	lp = dic_lp[mp]
	rp = dic_rp[mp]
	sum1 = slist[lp]
	sum2 = slist[mp] - slist[lp]
	sum3 = slist[rp] - slist[mp]
	sum4 = slist[-1] - slist[rp]
	sum_list = [sum1, sum2, sum3, sum4]
	sum_list.sort()
	diff = sum_list[-1] - sum_list[0]
	if diff < min_diff:
		min_diff = diff
print(min_diff)


import sys, os
from itertools import accumulate
import bisect
f = lambda : list(map(int, input().split()))
if 'local' in os.environ:
	sys.stdin = open('./input.txt', 'r')
n = f()[0]

def get_mid(b, i):
	nonlocal n
	front_i_sum = b[i]
	idx1 = bisect.bisect_right(b, front_i_sum / 2)
	if idx1 == 0:
		idx1 = 1
		max_fisrt = max(b[0], b[i] - b[0])
		min_first = min(b[0], b[i] - b[0])
	else:
		max1 = b[idx1]
		min1 = b[i] - b[idx1]
		max2 = b[i] - b[idx1 - 1]
		min2 = b[idx1 - 1]
		if max1 - min1 >= max2 - min2:
			max_fisrt = max2
			min_first = min2
		else:
			max_fisrt = max1
			min_first = min1
	idx2 = bisect.bisect_right(b, front_i_sum + (b[n - 1] - b[i]) / 2)
	if idx2 == i + 1:
		max_s = max(b[i + 1] - b[i], b[n - 1] - b[i + 1])
		min_s = min(b[i + 1] - b[i], b[n - 1] - b[i + 1])
	else:
		max1 = b[idx2] - front_i_sum
		min1 = b[n - 1] - b[idx2]
		max2 = b[n - 1] - b[idx2 - 1]
		min2 = b[idx2 - 1] - front_i_sum
		if max1 - min1 >= max2 - min2:
			max_s = max2
			min_s = min2
		else:
			max_s = max1
			min_s = min1
	return max(max_fisrt, max_s) - min(min_first, min_s)

def solve():
	a = f()
	b = list(accumulate(a))
	ans = int(200000000000000.0)
	for i in range(1, n - 2):
		ans = min(ans, get_mid(b, i))
	print(ans)
solve()


import sys

def cumsum(li):
	ret = [0]
	sum = 0
	for i in li:
		sum += i
		ret.append(sum)
	return ret
sys.setrecursionlimit(10000)
INF = float('inf')
N = int(input())
A = list(map(int, input().split()))
cs = cumsum(A)
assert len(cs) == N + 1

def calc_diff(d1, d2, d3):
	diffs = [cs[d1] - cs[0], cs[d2] - cs[d1], cs[d3] - cs[d2], cs[N] - cs[d3]]
	return max(diffs) - min(diffs)
d0 = 0
d1 = 1
d2 = 2
d3 = 3
d4 = N
ans = INF
while d2 < d4 - 1:
	d012 = abs(cs[d1] - cs[d0] - (cs[d2] - cs[d1]))
	while d1 < d2 - 1 and d012 > abs(cs[d1 + 1] - cs[d0] - (cs[d2] - cs[d1 + 1])):
		d1 += 1
		d012 = abs(cs[d1] - cs[d0] - (cs[d2] - cs[d1]))
	d234 = abs(cs[d3] - cs[d2] - (cs[d4] - cs[d3]))
	while d3 < d4 - 1 and d234 > abs(cs[d3 + 1] - cs[d2] - (cs[d4] - cs[d3 + 1])):
		d3 += 1
		d234 = abs(cs[d3] - cs[d2] - (cs[d4] - cs[d3]))
	ans = min(ans, calc_diff(d1, d2, d3))
	d2 += 1
print(ans)


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)


import bisect
N = int(input())
A = list((int(a) for a in input().split()))
Acum = [0] * (N + 1)
for i in range(N):
	Acum[i + 1] = Acum[i] + A[i]
ans = 10 ** 18
for i in range(2, N - 1):
	B = bisect.bisect_left(Acum, Acum[i] // 2) - 1
	if abs(Acum[B] * 2 - Acum[i]) > abs(Acum[B + 1] * 2 - Acum[i]):
		B += 1
	if B == i:
		B -= 1
	elif B == 0:
		B += 1
	P = Acum[B]
	Q = Acum[i] - Acum[B]
	D = bisect.bisect_left(Acum, Acum[i] + (Acum[-1] - Acum[i]) // 2) - 1
	if abs(Acum[D] * 2 - Acum[i] - Acum[-1]) > abs(Acum[D + 1] * 2 - Acum[i] - Acum[-1]):
		D += 1
	if D == N:
		D -= 1
	elif D == i:
		D += 1
	R = Acum[D] - Acum[i]
	S = Acum[-1] - Acum[D]
	mi = min(P, Q, R, S)
	ma = max(P, Q, R, S)
	ans = min(ans, abs(ma - mi))
print(ans)


from statistics import mean
N = int(input())
A = list(map(int, input().split()))
S = [A[0]]
for i in range(1, N):
	S.append(S[i - 1] + A[i])
left_middle = 0
right_middle = 2
ans = float('inf')
for middle in range(1, N - 2):
	left_sum = S[left_middle]
	right_sum = S[middle] - left_sum
	diff = abs(left_sum - right_sum)
	for i in range(left_middle + 1, middle):
		left_sum = S[i]
		right_sum = S[middle] - left_sum
		if diff > abs(left_sum - right_sum):
			left_middle = i
			diff = abs(left_sum - right_sum)
		else:
			break
	left_sum = S[right_middle] - S[middle]
	right_sum = S[-1] - S[right_middle]
	diff = abs(left_sum - right_sum)
	for i in range(right_middle + 1, N):
		left_sum = S[i] - S[middle]
		right_sum = S[-1] - S[i]
		if diff > abs(left_sum - right_sum):
			right_middle = i
			diff = abs(left_sum - right_sum)
		else:
			break
	s1 = S[left_middle]
	s2 = S[middle] - s1
	s3 = S[right_middle] - s1 - s2
	s4 = S[-1] - s1 - s2 - s3
	score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
	ans = min(ans, score)
print(ans)


from itertools import accumulate as ac
n = int(input())
s = list(ac(list(map(int, input().split()))))
c = 0
d = 2
f = s[-1]
k = f
for i in range(1, n - 1):
	while s[i] > s[c] + s[c + 1]:
		c += 1
	while s[i] + f > s[d] + s[d + 1]:
		d += 1
	j = [s[c], s[i] - s[c], s[d] - s[i], f - s[d]]
	k = min(max(j) - min(j), k)
print(k)


from itertools import accumulate

def solve(string):
	(n, *a) = list(map(int, string.split()))
	(*a,) = accumulate(a)
	(l, r, e) = (0, 2, a[-1])
	ans = e
	for c in a[1:-2]:
		while a[l] + a[l + 1] < c:
			l += 1
		while a[r] + a[r + 1] < c + e:
			r += 1
		tmp = sorted([a[l], c - a[l], a[r] - c, e - a[r]])
		ans = min(ans, tmp[-1] - tmp[0])
	return str(ans)

def __starting_point():
	print(solve('\n'.join([input(), input()])))
__starting_point()


N = int(input())
A_list = [int(i) for i in input().split()]
Total_list = []
s = 0
for num in A_list:
	s += num
	Total_list.append(s)
L = 0
R = 2
ans = Total_list[N - 1] + 1
for Mid in range(1, N - 2):
	sum_L = Total_list[Mid]
	sum_R = Total_list[N - 1] - sum_L
	while abs(sum_L - 2 * Total_list[L]) > abs(sum_L - 2 * Total_list[L + 1]):
		L += 1
	while abs(Total_list[N - 1] - Total_list[R] - (Total_list[R] - sum_L)) > abs(Total_list[N - 1] - Total_list[R + 1] - (Total_list[R + 1] - sum_L)):
		R += 1
	P = Total_list[L]
	Q = sum_L - Total_list[L]
	S = Total_list[R] - sum_L
	T = Total_list[N - 1] - Total_list[R]
	ans = min(ans, max(P, Q, S, T) - min(P, Q, S, T))
print(ans)


(n, *a) = map(int, open(0).read().split())
for i in range(n - 1):
	a[i + 1] += a[i]
(j, k, m) = (0, 2, 1e+18)
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])
	m = min(m, max(t) - min(t))
print(m)


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)


from itertools import accumulate, islice
from bisect import bisect_left
n = int(input())
xs = list(map(int, input().split()))
ys = list(accumulate(xs))
(zs, total) = (ys[:-1], ys[-1])
res = max(xs) - min(xs)
for (i, z) in islice(enumerate(zs), 1, n - 1):
	j = bisect_left(zs, z // 2)
	splits = ((zs[j + k], z - zs[j + k]) for k in (-1, 0, 1) if 0 <= j + k <= i)
	(a, b) = min(splits, key=lambda s: abs(s[0] - s[1]))
	j = bisect_left(zs, (total - z) // 2 + z)
	splits = ((zs[j + k] - z, total - zs[j + k]) for k in (-1, 0, 1) if i <= j + k <= n - 2)
	(c, d) = min(splits, key=lambda s: abs(s[0] - s[1]))
	(minn, _, _, maxx) = sorted((a, b, c, d))
	if maxx - minn < res:
		res = maxx - minn
print(res)


N = int(input())
A = tuple(map(int, input().split()))
from itertools import accumulate
CA = list(accumulate(A))
mindiff = CA[-1]
left = 0
right = 2
for c in range(1, N - 1):
	p = CA[left]
	q = CA[c] - CA[left]
	while True:
		pi = CA[left + 1]
		qi = CA[c] - CA[left + 1]
		if abs(pi - qi) >= abs(p - q):
			break
		p = pi
		q = qi
		left += 1
	r = CA[right] - CA[c]
	s = CA[-1] - CA[right]
	while True:
		ri = CA[right + 1] - CA[c]
		si = CA[-1] - CA[right + 1]
		if abs(ri - si) >= abs(r - s):
			break
		r = ri
		s = si
		right += 1
	mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)


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)


N = int(input())
A = list(map(int, input().split()))
S = [0]
for (i, a) in enumerate(A, 1):
	S.append(S[i - 1] + a)
Sn = S[-1]
ans = Sn
i0 = 1
k0 = 3
for j in range(2, N - 1):
	tmpS = S[j]
	for i in range(i0, j):
		if S[i] > tmpS / 2:
			break
	i -= abs(tmpS - S[i] - S[i]) > abs(tmpS - S[i - 1] - S[i - 1])
	i0 = i
	for k in range(k0, N):
		if S[k] - tmpS > (Sn - tmpS) / 2:
			break
	k -= abs(Sn - S[k] - S[k] + tmpS) > abs(Sn - S[k - 1] - S[k - 1] + tmpS)
	k0 = k
	P = (S[i], S[j] - S[i], S[k] - S[j], S[-1] - S[k])
	ans = min(ans, max(P) - min(P))
print(ans)


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)


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)


from itertools import accumulate
from bisect import bisect_left

def main():
	(N, *A) = list(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()


def main():
	N = int(input())
	A = list(map(int, input().split()))
	S = [0] * len(A)
	s = 0
	for (i, a) in enumerate(A):
		s += a
		S[i] = s
	l = 0
	b = 2
	m = S[-1]
	for c in range(1, N - 2):
		(p, q) = (S[l], S[c] - S[l])
		while l + 1 < c:
			(pn, qn) = (S[l + 1], S[c] - S[l + 1])
			if abs(pn - qn) >= abs(p - q):
				break
			(p, q) = (pn, qn)
			l += 1
		if b <= c:
			b = c + 1
		(r, s) = (S[b] - S[c], S[-1] - S[b])
		while b + 1 < N - 1:
			(rn, sn) = (S[b + 1] - S[c], S[-1] - S[b + 1])
			if abs(rn - sn) >= abs(r - s):
				break
			(r, s) = (rn, sn)
			b += 1
		m = min(m, max(p, q, r, s) - min(p, q, r, s))
	return m
print(main())


import sys
from itertools import accumulate
(n, *a) = map(int, sys.stdin.read().split())

def main():
	ans = float('inf')
	left = 0
	right = 2
	p = a[0]
	q = 0
	r = sum(a[1:3])
	s = sum(a[3:])
	for c in range(1, n - 2):
		q += a[c]
		r -= a[c]
		while left < c - 1:
			nex = a[left + 1]
			if abs(q - nex - (p + nex)) <= abs(q - p):
				q -= nex
				p += nex
				left += 1
			else:
				break
		while right < n - 2:
			nex = a[right + 1]
			if abs(s - nex - (r + nex)) <= abs(s - r):
				s -= nex
				r += nex
				right += 1
			else:
				break
		res = sorted([p, q, r, s])
		ans = min(ans, res[-1] - res[0])
	return ans

def __starting_point():
	ans = main()
	print(ans)
__starting_point()


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
bl = [0]
for i in a:
	bl.append(bl[-1] + i)
br = [0]
for i in a[::-1]:
	br.append(br[-1] + i)

def fl(r):
	suma = bl[r + 1]
	ir = bisect_left(bl, suma // 2)
	(ans11, ans12) = (bl[ir], suma - bl[ir])
	(ans21, ans22) = (bl[ir - 1], suma - bl[ir - 1])
	if abs(ans11 - ans12) < abs(ans21 - ans22):
		return [ans11, ans12]
	else:
		return [ans21, ans22]

def fr(l):
	r = n - 1 - l
	suma = br[r + 1]
	ir = bisect_left(br, suma // 2)
	(ans11, ans12) = (br[ir], suma - br[ir])
	(ans21, ans22) = (br[ir - 1], suma - br[ir - 1])
	if abs(ans11 - ans12) < abs(ans21 - ans22):
		return [ans11, ans12]
	else:
		return [ans21, ans22]
ans = 10 ** 20
for i in range(1, n - 1):
	l = i
	r = i + 1
	(ll, lr) = fl(i)
	(rl, rr) = fr(i + 1)
	ans = min(ans, max(ll, lr, rl, rr) - min(ll, lr, rl, rr))
print(ans)


def main():
	from bisect import bisect_left
	n = int(input())
	a = list(map(int, input().split()))
	cs = [0] * n
	for i in range(n):
		cs[i] = cs[i - 1] + a[i]
	ans = 10 ** 15
	for middle in range(2, n - 1):
		first = bisect_left(cs, cs[middle - 1] // 2, lo=1, hi=middle)
		if abs(cs[middle - 1] - cs[first - 1] - cs[first - 1]) < abs(cs[middle - 1] - cs[first] - cs[first]):
			p = cs[first - 1]
			q = cs[middle - 1] - cs[first - 1]
		else:
			p = cs[first]
			q = cs[middle - 1] - cs[first]
		last = bisect_left(cs, (cs[-1] + cs[middle - 1]) // 2, lo=middle + 1, hi=n)
		if abs(cs[-1] - cs[last - 1] - (cs[last - 1] - cs[middle - 1])) < abs(cs[-1] - cs[last] - (cs[last] - cs[middle - 1])):
			r = cs[last - 1] - cs[middle - 1]
			s = cs[-1] - cs[last - 1]
		else:
			r = cs[last] - cs[middle - 1]
			s = cs[-1] - cs[last]
		diff = max(p, q, r, s) - min(p, q, r, s)
		if diff < ans:
			ans = diff
	print(ans)
main()


N = int(input())
A = list(map(int, input().split()))
tmp = 0
lr = [0]
for a in A:
	tmp += a
	lr.append(tmp)
ans = float('inf')
(f, g) = (1, 3)
for i in range(2, N - 1):
	while abs(lr[i] - lr[f] - lr[f]) > abs(lr[i] - lr[f + 1] - lr[f + 1]):
		f += 1
	while abs(lr[-1] - lr[g] - (lr[g] - lr[i])) > abs(lr[-1] - lr[g + 1] - (lr[g + 1] - lr[i])):
		g += 1
	l = (lr[f], lr[i] - lr[f], lr[-1] - lr[g], lr[g] - lr[i])
	ans = min(ans, max(l) - min(l))
print(ans)


from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
X = list(accumulate(A))
l = 0
L = [-1] * N
for m in range(2, N - 1):
	target = X[m - 1] / 2
	while l + 1 <= m and abs(target - X[l]) >= abs(target - X[l + 1]):
		l += 1
	L[m] = l
r = N - 1
r_sum = 0
R = [-1] * N
for m in reversed(list(range(2, N - 1))):
	target = (X[-1] - X[m - 1]) / 2
	while r - 1 >= m and abs(target - r_sum) >= abs(target - (r_sum + A[r])):
		r_sum += A[r]
		r -= 1
	R[m] = r
ans = float('inf')
for m in range(2, N - 1):
	(li, ri) = (L[m], R[m])
	(B, C, D, E) = (X[li], X[m - 1] - X[li], X[ri] - X[m - 1], X[-1] - X[ri])
	ans = min(ans, max(B, C, D, E) - min(B, C, D, E))
print(ans)


n = int(input())
a = list(map(int, input().split()))
left = []
now = a[0]
le = 1
s = a[0]
for i in range(1, n):
	s += a[i]
	while le < i and abs(2 * now - s) > abs(2 * now + 2 * a[le] - s):
		now += a[le]
		le += 1
	left.append([now, s - now])
right = []
now = a[-1]
ri = 2
s = a[-1]
for i in range(2, n + 1):
	s += a[-i]
	while ri < i and abs(2 * now - s) > abs(2 * now + 2 * a[-ri] - s):
		now += a[-ri]
		ri += 1
	right.append([now, s - now])
ans = float('INF')
for i in range(n - 3):
	(a, b) = left[i]
	(c, d) = right[n - 4 - i]
	ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
print(ans)


import sys
from itertools import accumulate
from bisect import bisect_left as bi_l
(n, *a) = map(int, sys.stdin.read().split())

def main():
	s = list(accumulate(a))
	ans = float('inf')
	for center in range(1, n - 2):
		pq = s[center]
		left = bi_l(s, pq / 2)
		if left == 0:
			p = s[0]
		else:
			if pq - s[left] < s[left - 1]:
				left -= 1
			p = s[left]
		q = pq - p
		rt = s[-1] - pq
		right = bi_l(s, pq + rt / 2)
		if right == center + 1:
			r = s[center + 1] - pq
		else:
			if rt - (s[right] - pq) < s[right - 1] - pq:
				right -= 1
			r = s[right] - pq
		t = rt - r
		res = sorted([p, q, r, t])
		ans = min(ans, res[-1] - res[0])
	return ans

def __starting_point():
	ans = main()
	print(ans)
__starting_point()


import bisect
from collections import deque
n = int(input())
A = list(map(int, input().split()))
S = [A[0]]
for i in range(n - 1):
	S.append(S[-1] + A[i + 1])
ans = 10 ** 15
A1 = deque([A[0]])
A2 = deque(A[1:n])
for i in range(2, n - 1):
	A1.append(A[i - 1])
	A2.popleft()
	if len(A1) == 2:
		M1 = max(A1)
		m1 = min(A1)
	else:
		x = bisect.bisect_left(S, S[i - 1] // 2, lo=0, hi=i + 1)
		M11 = max(S[x - 1], S[i - 1] - S[x - 1])
		m11 = min(S[x - 1], S[i - 1] - S[x - 1])
		M12 = max(S[x], S[i - 1] - S[x])
		m12 = min(S[x], S[i - 1] - S[x])
		M1 = min(M11, M12)
		m1 = max(m11, m12)
	if len(A2) == 2:
		M2 = max(A2)
		m2 = min(A2)
	else:
		x = bisect.bisect_left(S, S[i - 1] + (S[-1] - S[i - 1]) // 2, lo=0, hi=n)
		M21 = max(S[x - 1] - S[i - 1], S[-1] - S[x - 1])
		m21 = min(S[x - 1] - S[i - 1], S[-1] - S[x - 1])
		M22 = max(S[x] - S[i - 1], S[-1] - S[x])
		m22 = min(S[x] - S[i - 1], S[-1] - S[x])
		M2 = min(M21, M22)
		m2 = max(m21, m22)
	a = max(M1, M2) - min(m1, m2)
	if a < ans:
		ans = a
print(ans)


from itertools import *
N = int(input())
A = list(accumulate(map(int, input().split())))
l = 0
r = 2
t = A[-1]
a = t
for m in A[1:-2]:
	while abs(t - 2 * A[r] + m) > abs(t - 2 * A[r + 1] + m):
		r += 1
	while abs(m - 2 * A[l]) > abs(m - 2 * A[l + 1]):
		l += 1
	x = sorted([A[l], m - A[l], A[r] - m, t - A[r]])
	a = min(a, x[3] - x[0])
print(a)


n = int(input())
a = list(map(int, input().split()))
accuml = [0] * n
accumr = [0] * n
accuml[0] = a[0]
accumr[0] = a[n - 1]
for i in range(n - 1):
	accuml[i + 1] += a[i + 1] + accuml[i]
	accumr[i + 1] += a[n - i - 2] + accumr[i]
ll = 0
rr = n - 3
ans = 10 ** 18
for i in range(1, n - 2):
	sl = accuml[i]
	sr = accumr[n - 2 - i]
	while abs(accuml[ll + 1] - sl / 2) < abs(accuml[ll] - sl / 2):
		ll += 1
	while abs(accumr[rr - 1] - sr / 2) < abs(accumr[rr] - sr / 2):
		rr -= 1
	maxi = max(sl - accuml[ll], accuml[ll], sr - accumr[rr], accumr[rr])
	mini = min(sl - accuml[ll], accuml[ll], sr - accumr[rr], accumr[rr])
	ans = min(ans, maxi - mini)
print(ans)


import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def main():
	N = int(input())
	A = list(map(int, input().split()))
	cumsum = list(accumulate([0] + A))
	ans = INF
	l = 0
	r = 2
	fl = lambda i, l: abs(cumsum[i + 1] - 2 * cumsum[l + 1])
	fr = lambda i, r: abs(cumsum[-1] - cumsum[i + 1] - 2 * (cumsum[r + 1] - cumsum[i + 1]))
	for i in range(1, N - 2):
		while fl(i, l + 1) < fl(i, l):
			l += 1
		while fr(i, r + 1) < fr(i, r):
			r += 1
		a = cumsum[l + 1]
		b = cumsum[i + 1] - a
		c = cumsum[r + 1] - a - b
		d = cumsum[-1] - a - b - c
		ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
	print(ans)

def __starting_point():
	main()
__starting_point()


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)


n = int(input())
A = list(map(int, input().split()))
S = [0]
cnt = 0
for i in range(n):
	cnt += A[i]
	S.append(cnt)
ans = S[n]
d1 = 1
d3 = 2
for d2 in range(2, n - 1):
	L = S[d2]
	R = S[n] - S[d2]
	for i in range(d1, d2):
		if S[i] >= L / 2:
			break
	if abs(S[i] - L / 2) >= abs(S[i - 1] - L / 2):
		d1 = i - 1
	else:
		d1 = i
	for i in range(d3, n):
		if S[i] - S[d2] >= R / 2:
			break
	if abs(S[i] - S[d2] - R / 2) >= abs(S[i - 1] - S[d2] - R / 2):
		d3 = i - 1
	else:
		d3 = i
	s = [S[d1], S[d2] - S[d1], S[d3] - S[d2], S[n] - S[d3]]
	ans = min(max(s) - min(s), ans)
print(ans)


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)


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)


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


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)


N = int(input())
A = list(map(int, input().split()))
s = 0
S = [0] * N
for (i, a) in enumerate(A):
	s += a
	S[i] = s
t = S[-1]
ans = 10 ** 20
j = 0
k = 2
for i in range(1, N - 2):
	s = S[i]
	while abs(s - 2 * S[j + 1]) < abs(s - 2 * S[j]):
		j += 1
	while abs(t - 2 * S[k + 1] + s) < abs(t - 2 * S[k] + s):
		k += 1
	v = (S[j], s - S[j], S[k] - s, t - S[k])
	ans = min(ans, max(v) - min(v))
print(ans)


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)


inf = float('inf')
N = int(input())
a = tuple(map(int, input().split()))
c_sum = [0]
t = 0
for aa in a:
	t += aa
	c_sum.append(t)
ans = inf
(p, q) = (0, 2)
for cut in range(2, N - 2 + 1):
	while p < cut - 1:
		if abs(c_sum[cut] - c_sum[p] * 2) >= abs(c_sum[cut] - c_sum[p + 1] * 2):
			p += 1
		else:
			break
	while q < N - 1:
		if abs(c_sum[N] - c_sum[q] - (c_sum[q] - c_sum[cut])) >= abs(c_sum[N] - c_sum[q + 1] - (c_sum[q + 1] - c_sum[cut])):
			q += 1
		else:
			break
	cands = [c_sum[cut] - c_sum[p], c_sum[p], c_sum[N] - c_sum[q], c_sum[q] - c_sum[cut]]
	ans = min(ans, max(cands) - min(cands))
print(ans)


n = int(input())
a = list(map(int, input().split()))
score = [a[0], 0, a[1] + a[2], sum(a[3:])]
ans = 10 ** 18
(i, k) = (1, 3)
for j in range(2, n - 1):
	score[1] += a[j - 1]
	score[2] -= a[j - 1]
	while abs(score[0] - score[1]) > abs(score[0] + a[i] - score[1] + a[i]):
		score[0] += a[i]
		score[1] -= a[i]
		i += 1
	while abs(score[2] - score[3]) > abs(score[2] + a[k] - score[3] + a[k]):
		score[2] += a[k]
		score[3] -= a[k]
		k += 1
	ans = min(ans, max(score) - min(score))
print(ans)


from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
c = list(accumulate(a))
ans = float('inf')
(x, y) = (0, 2)
for i in range(1, n - 2):
	while c[x] < c[i] - c[x + 1]:
		x += 1
	y = max(y, i + 1)
	while c[y] - c[i] < c[-1] - c[y + 1]:
		y += 1
	ma = max(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
	mi = min(c[x], c[i] - c[x], c[y] - c[i], c[-1] - c[y])
	ans = min(ans, ma - mi)
print(ans)


import sys
import itertools
INF = float('inf')

def solve(N: int, A: 'List[int]'):
	wa = list(itertools.accumulate(A))
	m = INF
	(atama1, atama2) = (0, 2)
	for i in range(1, N - 2):
		(s0, s1) = (wa[atama1], wa[i] - wa[atama1])
		for j in range(atama1 + 1, i):
			(t0, t1) = (wa[j], wa[i] - wa[j])
			if t0 >= t1:
				if abs(s1 - s0) >= abs(t1 - t0):
					(s0, s1) = (t0, t1)
					atama1 += 1
				break
			(s0, s1) = (t0, t1)
			atama1 += 1
		(s2, s3) = (wa[atama2] - wa[i], wa[N - 1] - wa[atama2])
		for j in range(atama2 + 1, N):
			(t2, t3) = (wa[j] - wa[i], wa[N - 1] - wa[j])
			if t2 >= t3:
				if abs(s3 - s2) >= abs(t3 - t2):
					(s2, s3) = (t2, t3)
					atama2 += 1
				break
			(s2, s3) = (t2, t3)
			atama2 += 1
		s = [s0, s1, s2, s3]
		s.sort()
		m = min(s[3] - s[0], m)
	print(m)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	A = [int(next(tokens)) for _ in range(N)]
	solve(N, A)

def __starting_point():
	main()
__starting_point()


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)


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)


from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = [0] + list(map(int, input().split()))
ans = float('inf')
A = list(accumulate(A))
for m in range(2, N - 1):
	Lx = A[m] // 2
	Li = bisect_left(A, Lx)
	if abs(Lx - A[Li]) > abs(Lx - A[Li - 1]):
		Li -= 1
	Rx = (A[-1] + A[m]) // 2
	Ri = bisect_left(A, Rx)
	if abs(Rx - A[Ri]) > abs(Rx - A[Ri - 1]):
		Ri -= 1
	(P, Q, R, S) = (A[Li], A[m] - A[Li], A[Ri] - A[m], A[-1] - A[Ri])
	tmp_ans = max(P, Q, R, S) - min(P, Q, R, S)
	ans = min(ans, tmp_ans)
print(ans)


def main():
	N = int(input())
	A = list(map(int, input().split(' ')))
	X = [0 for _ in range(N + 1)]
	for i in range(N):
		X[i + 1] = X[i] + A[i]
	ans = 10 ** 10
	left = 0
	right = 2
	for i in range(1, N):
		while left < i:
			d = abs(X[left] - (X[i] - X[left]))
			d_next = abs(X[left + 1] - (X[i] - X[left + 1]))
			if d_next > d:
				break
			left += 1
		while right < N:
			d = abs(X[N] - X[right] - (X[right] - X[i]))
			d_next = abs(X[N] - X[right + 1] - (X[right + 1] - X[i]))
			if d_next > d:
				break
			right += 1
		(p, q, r, s) = (X[left], X[i] - X[left], X[right] - X[i], X[N] - X[right])
		ans = min([ans, max([p, q, r, s]) - min([p, q, r, s])])
	print(ans)

def __starting_point():
	main()
__starting_point()


from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
	tmp = 0
	for i in range(N):
		tmp += abs(a[i] - a[n - 1])
	return tmp
N = int(input())
a = list(acc(map(int, input().split())))
ans = a[-1]
p = 0
q = 2
for j in range(1, N - 2):
	q = max(q, j + 1)
	while p < j - 1 and abs(a[j] - a[p] * 2) > abs(a[j] - a[p + 1] * 2):
		p += 1
	while q < N - 2 and abs(a[j] + a[N - 1] - a[q] * 2) > abs(a[j] + a[N - 1] - a[q + 1] * 2):
		q += 1
	x = [a[p], a[j] - a[p], a[q] - a[j], a[N - 1] - a[q]]
	ans = min(ans, max(x) - min(x))
print(ans)


from itertools import accumulate as ac
N = int(input())
A = list(ac(list(map(int, input().split()))))
(l, r, t) = (0, 2, A[-1])
c = t
for m in A[1:-2]:
	while t + m > A[r] + A[r + 1]:
		r += 1
	while m > A[l] + A[l + 1]:
		l += 1
	x = sorted([A[l], m - A[l], A[r] - m, t - A[r]])
	c = min(c, x[-1] - x[0])
print(c)


N = int(input())
A = list(map(int, input().split()))
cul_sum = [0 for _ in range(N + 1)]
for i in range(N):
	cul_sum[i + 1] = A[i] + cul_sum[i]

def diff_left(center, left):
	return abs(cul_sum[center + 1] - 2 * cul_sum[left + 1])

def diff_right(center, right):
	return abs(cul_sum[N] - 2 * cul_sum[right + 1] + cul_sum[center + 1])
L = [-1 for _ in range(N - 1)]
R = [-1 for _ in range(N - 1)]
l = 0
r = 2
ans = float('inf')
for i in range(1, N - 2):
	while l < i and diff_left(i, l) > diff_left(i, l + 1):
		l += 1
	if r <= i:
		r = i + 1
	while r < N and diff_right(i, r) > diff_right(i, r + 1):
		r += 1
	part_sum = [cul_sum[l + 1], cul_sum[i + 1] - cul_sum[l + 1], cul_sum[r + 1] - cul_sum[i + 1], cul_sum[N] - cul_sum[r + 1]]
	ans = min(ans, max(part_sum) - min(part_sum))
print(ans)


import math
n = int(input())
a = [int(i) for i in input().split(' ')]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)
li = 0
ri = n
for i in range(1, n + 1):
	s[i] = a[i] + s[i - 1]
	sr[i] = ar[i] + sr[i - 1]

def f(a):
	return max(a) - min(a)

def fs(rr):
	nonlocal li
	while abs(s[rr] - 2 * s[li]) > abs(s[rr] - 2 * s[li + 1]):
		li += 1

def fsr(rr):
	nonlocal ri
	while abs(sr[rr] - 2 * sr[ri]) > abs(sr[rr] - 2 * sr[ri - 1]):
		ri -= 1
m_min = 2 * 10 ** 14
for i in range(2, n - 1):
	fs(i)
	fsr(n - i)
	m = f([s[li], s[i] - s[li], sr[ri], sr[n - i] - sr[ri]])
	if m < m_min:
		m_min = m
print(m_min)


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


import sys

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 list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(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 list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
l = 1
m = 2
r = 3
a = sum(A[:l])
b = sum(A[l:m])
c = sum(A[m:r])
d = sum(A[r:])
ans = max(a, b, c, d) - min(a, b, c, d)
while m < N - 1:
	while l < m - 1 and abs(a - b) > abs(a + A[l] - (b - A[l])):
		a += A[l]
		b -= A[l]
		l += 1
	while r < N - 1 and abs(c - d) > abs(c + A[r] - (d - A[r])):
		c += A[r]
		d -= A[r]
		r += 1
	ans = min(ans, max(a, b, c, d) - min(a, b, c, d))
	b += A[m]
	c -= A[m]
	m += 1
	if m == r:
		c += A[r]
		d -= A[r]
		r += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
	b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
	while True:
		if i == j + 1:
			x[i - 2][0] = b[j]
			break
		if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
			j += 1
		else:
			x[i - 2][0] = b[j]
			break
j = n - 1
for i in range(n - 2, 1, -1):
	while True:
		if i == j - 1:
			x[i - 2][1] = b[j]
			break
		if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
			j -= 1
		else:
			x[i - 2][1] = b[j]
			break
ans = 1145141919810
for i in range(n - 3):
	s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
	ans = min(ans, max(s) - min(s))
print(ans)


n = int(input())
a_list = [int(x) for x in input().split()]
temp_list = [0] * (n + 1)
for i in range(1, n + 1):
	temp_list[i] = a_list[i - 1] + temp_list[i - 1]
l = 1
r = 3
ans = temp_list[-1]
for m in range(2, n - 1):
	gap_min = abs(temp_list[m] - temp_list[l] - (temp_list[l] - temp_list[0]))
	while l < m:
		l += 1
		gap = abs(temp_list[m] - temp_list[l] - (temp_list[l] - temp_list[0]))
		if gap < gap_min:
			gap_min = gap
		else:
			l -= 1
			break
	else:
		l -= 1
	gap_min = abs(temp_list[n] - temp_list[r] - (temp_list[r] - temp_list[m]))
	while r < n:
		r += 1
		gap = abs(temp_list[n] - temp_list[r] - (temp_list[r] - temp_list[m]))
		if gap < gap_min:
			gap_min = gap
		else:
			r -= 1
			break
	else:
		r -= 1
	num_list = sorted([temp_list[l] - temp_list[0], temp_list[m] - temp_list[l], temp_list[r] - temp_list[m], temp_list[n] - temp_list[r]])
	ans_temp = num_list[3] - num_list[0]
	if ans_temp < ans:
		ans = ans_temp
print(ans)


N = int(input())
A = list(map(int, input().split()))
from itertools import accumulate
P = list(accumulate(A))
(l, right) = (0, 2)
diff = float('inf')
for c in range(1, N - 1):
	p = P[l]
	q = P[c] - P[l]
	while True:
		if abs(p + 2 * A[l + 1] - q) >= abs(p - q):
			break
		p = P[l + 1]
		q = P[c] - P[l + 1]
		l += 1
	r = P[right] - P[c]
	s = P[-1] - P[right]
	while True:
		if abs(r + 2 * A[right + 1] - s) >= abs(r - s):
			break
		r = P[right + 1] - P[c]
		s = P[-1] - P[right + 1]
		right += 1
	diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
print(diff)