← 返回题目列表

AtCoder · arc100_b

D. 等切

中文机器翻译题面 查看原题

分数: 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