Background

Special for beginners, ^_^

Description

如果一个点在一条线段上(包括这个点是线段端点的情况)，我们说“这条线段覆盖了这个点”。

现有个在一条水平直线上排列的点，请你编写程序计算一下：如果用3条线段覆盖所有的点（起点终点都是整数），这3条线段的长度之和最小是多少?

注意：既然说是3条，当然就不允许某两条是首尾相接的，否则就是2条了，而且,任何线段的长度都要大于0。

Format

Input

本题包含多组测试例。

对于每组测试例：

第一行为整数n(≤10000)，表示点的数量。

第二行有n-1个正整数，表示其它各点到最左端的点的距离。已知这些整数都不会超过int。

每个测试点的n求和不超过1e6。

Output

每行一个整数，表示用3条线段覆盖所有点时，其长度之和的最小值。

Samples

6
1 4 10 15 17
6
1 2 3 4 5

7
3

Limitation

1s, 1024KiB for each test case.