D - 等分

分数：$600$ 分

问题描述

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

他将在 $A$ 中进行三次切割，将其分成四个（非空的）连续子序列 $B,C,D,E$。 切割的位置可以任意选择。

设 $P,Q,R,S$ 分别为 $B,C,D,E$ 中元素之和。 当 $P,Q,R,S$ 的最大值和最小值之间的差绝对值较小时，Snuke 更加高兴。 找出 $P,Q,R,S$ 的最大值和最小值之间可能的最小差绝对值。

限制

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

输入

输入以以下格式从标准输入中给出：

$N$

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

输出

找出 $P,Q,R,S$ 的最大值和最小值之间可能的最小差绝对值。

5
3 2 4 1 2

2

如果我们将 $A$ 划分为 $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