P. 缓变序列

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们定义一个长度为 $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

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

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