你需要推平沿一条长直道路分布的建筑物。这些建筑物被建模为无限长直线上均匀分布的相同方形块堆。你强大的推土机可以将这些块中的任意一个向左或向右移动一个单位距离。这可能会将其他块推开，而位于移动块上方的块也会随之移动。被推过空隙的块会下落，直到接触地面或其他块。

例如，考虑下图 B.1 左侧所示的块堆。如果你将标记为 C 的块向右推，块 D 和 E 会被推向右侧，因为它们挡住了去路。块 A、B 和 F 也会随之移动，因为它们位于移动块的上方。在将 C 向右推后，E 会悬空，因此 E 和 F 会下落以填补空隙。结果如图 B.1 中间所示。将块 C 再向右推一步，就会得到右侧所示的配置。

你的目标是平整所有建筑物：进行推土作业，直到所有堆的高度最多为 1，即所有块都位于地面上。注意，道路在两侧无限延伸，因此这总是可能的。

给定堆的初始高度，确定将所有建筑物平整所需的最少移动次数，其中一次移动是指使用推土机将一个块向左或向右推一步。

图 B.1：块堆配置的示意图，以及将标记为 C 的块向右推两次后的结果（标记为 A–F 的块仅用于说明目的）。

输入格式

输入包含： 一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示块堆的数量。 一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$，对于每个 $i$)，表示从左到右各堆的初始高度。

图 B.1 左侧所示的示例可以表示为 3, 5, 3, 4, 1, 1, 0, 0, 1, 1，但也可以在左侧或右侧填充额外的零。

输出格式

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

样例

样例输入 1

5
1 1 2 1 1

样例输出 1

2

样例输入 2

5
1 4 3 1 1

样例输出 2

7

样例输入 3

9
1 0 0 0 6 0 0 0 1

样例输出 3

5

样例输入 4

10
1 3 0 0 1 9 1 1 1 1

样例输出 4

13