背景

译自 Northwestern Europe Regional Contest (NWERC) 2020。

题目描述

你的任务是推平一些位于一条又长又直的道路旁的建筑。我们把这些建筑建模为：在一条无限长的直线上，等间距摆放着若干堆完全相同的正方形积木。你的强力推土机可以把任意一块积木向左或向右移动一个单位距离。这可能会把其他挡路的积木一起推开，而放在正在移动的积木上方的积木也会跟着一起移动。如果某些积木被推到了空隙上方，它们会下落，直到落到地面或另一块积木上。

例如，考虑下图 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$。

输出格式

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

5
1 1 2 1 1

2

5
1 4 3 1 1

7

9
1 0 0 0 6 0 0 0 1

5

10
1 3 0 0 1 9 1 1 1 1

13

提示

【数据规模与约定】

• $1 \le n \le 2\cdot 10^5$。
• $0 \le a_i \le 10^9$。