P17027 [NWERC 2020] 推土机 / Bulldozer

译自 [Northwestern Europe Regional Contest (NWERC) 2020](http://2020.nwerc.eu)。

你的任务是推平一些位于一条又长又直的道路旁的建筑。我们把这些建筑建模为：在一条无限长的直线上，等间距摆放着若干堆完全相同的正方形积木。你的强力推土机可以把任意一块积木向左或向右移动一个单位距离。这可能会把其他挡路的积木一起推开，而放在正在移动的积木上方的积木也会跟着一起移动。如果某些积木被推到了空隙上方，它们会下落，直到落到地面或另一块积木上。 例如，考虑下图 B.1 左侧所示的积木堆。如果你把标记为 C 的积木向右推，那么标记为 D 和 E 的积木会因为挡在路上而一起向右移动。标记为 A、B 和 F 的积木也会跟着移动，因为它们位于正在移动的积木上方。把 C 向右推一次后，E 会位于一个空隙上方，因此 E 和 F 会下落来填补这个空隙。得到的积木堆如图 B.1 中间所示。如果再把 C 向右推一步，就会得到图 B.1 右侧的状态。 你的目标是把所有建筑“整平”：也就是说，不断推土，直到所有积木堆的高度都至多为 $1$，即所有积木都在地面上。注意，道路在左右两侧都是无限延伸的，所以这件事总是可以做到。 给定初始时各堆积木的高度，请求出为了整平所有建筑，最少需要多少次移动。一次移动指的是使用推土机把一块积木向左或向右推动一步。 :::align{center}    ::: 图 B.1：一组积木堆的状态，以及将标记为 C 的积木向右推动两次后的结果。标记为 A--F 的积木仅为了说明而进行了着色和标注。

输入包括： - 第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示积木堆的数量。 - 第二行包含 $n$ 个整数 $a_1,\ldots,a_n$（对每个 $i$，有 $0 \le a_i \le 10^9$），表示从左到右各堆积木的初始高度。 图 B.1 左侧的例子可以用 $3,5,3,4,1,1,0,0,1,1$ 表示，不过也可以在左侧或右侧额外补上一些 $0$。

输出整平所有建筑所需的最少移动次数。

【数据规模与约定】 - $1 \le n \le 2\cdot 10^5$。 - $0 \le a_i \le 10^9$。