题目内容

车间里有一根已经按节编号的管材，共 $m$ 节，从左到右第 $i$ 节的价值是 $v_i$。现在要在节与节之间切三刀，分成四段非空连续管，交给四个工班。一段的价值等于它包含的各节价值之和。

工班希望尽量均分：四段价值里的最大值减最小值要尽可能小。请算出这个最小差值。

约束：

• 4 $\le$ $m$ $\le$ 100000
• 1 $\le$ $v_i$ $\le$ 1000000000

输入描述

第一行一个整数 $m$（4 $\le$ $m$ $\le$ 100000），表示节数。

第二行 $m$ 个整数 $v_1,v_2,\ldots,v_m$（1 $\le$ $v_i$ $\le$ 1000000000），表示各节价值。

输出描述

输出一个整数，即四段价值最大值与最小值之差的最小可能值。

样例1

输入

5
4 5 1 2 8

输出

5

说明

切成 [4]、[5]、[1,2]、[8]，四段价值为 4、5、3、8，最大减最小为 5。这是最小可能差值。

样例2

输入

4
1 1 1 1

输出

0

说明

只有一种切法，四段都是 1，差值为 0。

样例3

输入

5
9 1 1 1 1

输出

8

说明

左边一节特别大。一种切法是 [9]、[1]、[1]、[1,1]，价值 9、1、1、2，差值为 8。其它切法不会更小。