分数: 600 点
问题陈述
Snuke 有一个整数序列 A 长度 N.
他将在 A 并将其分为四个(非空)连续子序列 B, C, D 和 E。 切割的位置可以自由选择。
让 P,Q,R,S 是元素的总和 分别是 B,C,D,E。 当最大和最小的绝对差值达到时,Snuke 会更快乐 P,Q,R,S 更小。 求其中最大值和最小值的最小可能绝对差 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.
示例输入 1
5 3 2 4 1 2
示例输出 1
2
如果我们除以 A as 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.
示例输入 2
10 10 71 84 33 6 47 23 25 52 64
示例输出 2
36
示例输入 3
7 1 2 3 1000000000 4 5 6
示例输出 3
999999994