均等切分

题目描述

Snuke君有一个长度为 $N$ 的整数序列 $A$。

Snuke君在 $A$ 的 $3$ 个位置切开，将其分解为 $4$ 个（非空的）连续子序列 $B,C,D,E$。 切的位置可以自由选择。

设整数序列 $B,C,D,E$ 的元素总和分别为 $P,Q,R,S$。 $P,Q,R,S$ 的最大值与最小值的差的绝对值越小，Snuke君越开心。 求 $P,Q,R,S$ 的最大值与最小值的差的绝对值可能达到的最小值。

输入格式

输入从标准输入以如下格式给出。

$N$
$A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $P,Q,R,S$ 的最大值与最小值的差的绝对值可能达到的最小值。

样例

5
3 2 4 1 2

2

若分割为 $B,C,D,E=(3),(2),(4),(1,2)$，则 $P=3,Q=2,R=4,S=1+2=3$。 此时，$P,Q,R,S$ 的最大值为 $4$，最小值为 $2$，其差的绝对值为 $2$。 无法让最大值与最小值的差的绝对值小于 $2$，所以答案为 $2$。

10
10 71 84 33 6 47 23 25 52 64

36

7
1 2 3 1000000000 4 5 6

999999994

数据范围

• $4 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数。