#6. Jumping 变换

由 $\text{Jumping}$ 变换可知:

$$\sum_{i=l}^r a_i$$

可以写成：

$${\frac{r}{\enspace 2 \enspace}}_{i=l} a_i$$

即：

$$\frac{ra_l}{2}$$

给定$a_i$，你需要把:

$$\sum_{i=1}^n a_i$$

写成:

$$\sum_{i=l_1}^{r_1} a_i+\sum_{i=l_2}^{r_2}a_i + \cdots + \sum_{i=l_k}^{r_k}a_i$$

并对每一项进行 $\text{Jumping}$ 变换，其中，$l_i \leq r_i, l_1 = 1, r_k = n, r_i = l_{i+1} - 1$。求变换后结果的最小值的两倍（为了防止浮点数带来的精度问题）。

形式化来说，给定数组$a_i$，你需要选择长度为$k$ ($1 \leq k \leq n$) 的数组 $l_i, r_i$， 满足 $l_i \leq r_i, l_1 = 1, r_k = n, r_i = l_{i+1} - 1$，使得 $\sum_{i=1}^{k} r_i a_{l_i}$ 最小化。

输入数据共两行，其中第一行仅包含一个整数 $n$，为数组 $a_i$ 的长度。

接下来一行包含 $n$ 个整数，由空格隔开，为数组 $a_i$。

输出仅一行一个整数，为答案。

样例输入1

6
1 1 4 5 1 4

样例输出1

6

原式可写成 $\sum_{i=1}^{6} a_i$，经过 $\text{Jumping}$ 变换，原式为 $\frac{6 \times a_1}{2}=3$，故答案是其两倍为 $主=6$。

样例输入2

8
1 9 -2 6 0 -8 -1 -7

样例输出2

-120

原式可写成 $\sum_{i=1}^{2} a_i + \sum_{i=3}^{5} a_i + \sum_{i=6}^{7} a_i +\sum_{i=8}^{8} a_i$，经过 $\text{Jumping}$ 变换，原式为 $\frac{1 \times 2}{2} + \frac{(-2)\times 5}{2} + \frac{(-8) \times 7}{2} + \frac{(-7) \times 8}{2}=-60$，故答案是其两倍为 $-120$。

样例输出3

90
1000000000 794328234 630957344 501187233 398107170 316227766 251188643 199526231 158489319 125892541 100000000 79432823 63095734 50118723 39810717 31622776 25118864 19952623 15848931 12589254 10000000 7943282 6309573 5011872 3981071 3162277 2511886 1995262 1584893 1258925 1000000 794328 630957 501187 398107 316227 251188 199526 158489 125892 100000 79432 63095 50118 39810 31622 25118 19952 15848 12589 10000 7943 6309 5011 3981 3162 2511 1995 1584 1258 1000 794 630 501 398 316 251 199 158 125 100 79 63 50 39 31 25 19 15 12 10 7 6 5 3 3 2 1 1 1

样例输入3

10273133530

$1 \leq n \leq 5 \times 10^3$

$-10^9 \leq a_i \leq 10^9$