题目描述

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$的最大值和最小值的绝对差的最小可能值。

示例输入 1

5
3 2 4 1 2

示例输出 1

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$。无法使$P,Q,R,S$的最大值和最小值的绝对差小于$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