问题描述

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

输入

第一行一个整数$N$,表示序列长度 第二行$N$个整数,表示整个序列

输出

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

5
3 2 4 1 2

2

10
10 71 84 33 6 47 23 25 52 64

36

7
1 2 3 1000000000 4 5 6

999999994

提示

$4≤N≤2×10^5$

$1≤A_i≤10^9$

输入中的所有值均为整数。

【样例1解析】

如果我们将 $A$ 划分为 $B,C,D,E=(3),(2),(4),(1,2)$，则 $P=3,Q=2,Q=4,S=1+2=3$。 在这里，$P,Q,R,S$ 的最大值和最小值分别为 $4$ 和 $2$，差的绝对值为 $2$。 我们不能使最大值和最小值的差绝对值小于$2$，所以答案是 $2$。