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

背景

stong9070是三国时代M国的一个谋士，某天他在落凤坡发现了一块黑黑的石头(远古陨石)，这个石头能量非常强大，瞬间stong9070就穿越到了30003年。在寻找回三国时代的路上遇到下大雨，路面坑坑洼洼，很不好走。30003年时代的路面非常特殊，都是由一些正立方块堆叠起的。 有的立方块坏了(立方块如果坏是全坏，不存在坏一点的情况)，里面就积水了。

题目描述

我们取路面的一个切面，可以使用一组正整数来描述，分别表示由正方体叠起的柱子的高度。若某高度值为 $x$，表示由 $x$ 个正立方的方块叠起（如下图）。

找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。

如图：柱子高度变化为 0 1 0 2 1 2 0 0 2 0

图中蓝色部分为积水面积，共有 6 个单位面积积水。

输入格式

第一行 $n$，表示有 $n$ 个数。

第 2 行连续 $n$ 个数表示依次由正方体叠起的高度，保证首尾为 0。

输出格式

一个数，可能积水的面积。

样例

10
0 1 0 2 1 2 0 0 2 0

6

17
0 7 21 24 23 21 28 15 24 20 21 29 17 6 7 14 0

51

数据范围

• $0 \le x \le 10000$
• $3 \le n \le 100000$