题目描述

给定一个整数序列 $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 (|B_i| + |C_i|)$ 的最小可能值。

输入格式

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

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

输出格式

请输出答案。

样例 1

输入

3
1 -2 3

输出

10

样例 2

输入

4
5 4 3 5

输出

17

样例 3

输入

1
-10

输出

10

说明/提示

限制条件

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

样例解释 1

可以取使得最小值的整数序列 $B, C$ 例如如下：

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

此时 $\sum\_{i=1}^N (|B\_i| + |C\_i|) = (0+1) + (0+2) + (5+2) = 10$。

样例解释 2

可以取使得最小值的整数序列 $B, C$ 例如如下：

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

样例解释 3

可以取使得最小值的整数序列 $B, C$ 例如如下：

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

由 ChatGPT 4.1 翻译