题目描述

我们定义一个长度为 $M$ 的序列 $A=(A_1,A_2,\ldots,A_M)$ 是“缓变序列”，当且仅当以下条件满足：

对于 $1 \le i < M$，均有 $|A_i - A_{i+1}| \le 1$。

现在 Shiro 拥有一个长度为 $N$ 的序列 $B=(B_1,B_2,\ldots,B_N)$，并且他可以无限次进行以下操作：

任意挑选序列中的某个整数，然后让其 $-1$。

他希望通过最少的操作次数来让序列 $B$ 变为一个“缓变序列”，问最少操作次数是多少？

输入格式

第一行包含一个正整数 $N$，表示序列长度。
第二行包含 $N$ 个整数 $B_1, B_2, \ldots, B_N$。

输出格式

一个整数，表示最少操作次数。

8
3 1 4 1 5 9 2 6

15

解释 #1

最终序列为 $\{2,1,2,1,2,3,2,3\}$。

数据范围

$1 \le N \le 3 \times 10^5$
$1 \le B_i \le 10^9$