题目描述

给定一个整数序列 $A = (A_1, \ldots, A_N)$。

考虑一对满足以下条件的整数序列 $B = (B_1, \ldots, B_N)$ 和 $C = (C_1, \ldots, C_N)$：

• 对于每个 $1 \leq i \leq N$，有 $A_i = B_i + C_i$；
• $B$ 是非递减的，即对于每个 $1 \leq i \leq N-1$，有 $B_i \leq B_{i+1}$；
• $C$ 是非递增的，即对于每个 $1 \leq i \leq N-1$，有 $C_i \geq C_{i+1}$。

找出使得 $\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr)$ 最小可能的值。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^8 \leq A_i \leq 10^8$

输入

从标准输入读入输入数据，输入格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出

输出结果。

示例输入1

3
1 -2 3

示例输出1

10

一个使得最小值的 $B = (B_1, \ldots, B_N)$ 和 $C = (C_1, \ldots, C_N)$ 如下所示：

• $B = (0, 0, 5)$,
• $C = (1, -2, -2)$。

这里有 $\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr) = (0+1) + (0+2) + (5+2) = 10$。

示例输入2

4
5 4 3 5

示例输出2

17

一个使得最小值的 $B$ 和 $C$如下所示：

• $B = (0, 1, 2, 4)$,
• $C = (5, 3, 1, 1)$。

示例输入3

1
-10

示例输出3

10

一个使得最小值的 $B$ 和 $C$ 如下所示：

• $B = (-3)$,
• $C = (-7)$。