题目描述

如果一个点在一条线段上（包括这个点是线段端点的情况），我们说"这条线段覆盖了这个点"。

我们有个在一条水平直线上排列的点。请你编写程序计算一下：如果用$\red{3}$条线段覆盖所有的点，这$\red{3}$条线段的长度之和最小是多少 ？注意：既然说是$\red{3}$条，当然就不允许某两条是首尾相接的，否则就是$\red{2}$条了，而且，任何线段的长度都要大于$\red{0}$。

输入格式

第一行为整数$\red{（6 <= n <= 100）}$，表示点的数量。

之后行，每行一个整数，表示其它各点到最左端的点的距离，单位是厘米。已知这些整数都不会超过$\red{40000}$。

输出格式

文件中只有一个整数，表示用$\red{3}$条线段覆盖所有点时，它们长度之和的最小值，单位是厘米。

样例

输入样例

6
1
4
10
15
17

输出样例

9