题目描述

すぬけ君は、長さ $N$ の整数列 $A$ を持っています。

すぬけ君は $A$ を $3$ 箇所で切って、$4$ つの（空でない）連続する部分列 $B,C,D,E$ に分解します。 切る位置は自由に選ぶことができます。

ここで、整数列 $B,C,D,E$ について、その要素の総和をそれぞれ $P,Q,R,S$ とおきます。 すぬけ君は、$P,Q,R,S$ の最大値と最小値の差の絶対値が小さいほど嬉しいです。 $P,Q,R,S$ の最大値と最小値の差の絶対値としてあり得る最も小さい値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$P,Q,R,S$ の最大値と最小値の差の絶対値としてあり得る最も小さい値を出力せよ。

题目大意

给定一个序列。要求把这个序列分成连续的四份，记这四份内数字和分别为 $a,b,c,d$ ，最小化 $a,b,c,d$ 的极差。

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\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数である。

Sample Explanation 1

$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$ が答えになります。