积水面积

题目描述

一组正整数,分别表示由正方体叠起的柱子的高度。若某高度值为 $x$,表示由 $x$ 个正立方的方块叠起(如下图,$0 \le x \le 5000$)。找出所有可能积水的地方(图中蓝色部分),统计它们可能积水的面积总和(计算的是图中的横截面积。一个立方体的位置,为一个单位面积)。 如图:柱子高度变化为 `0 1 0 2 1 2 0 0 2 0`。 ![](https://cdn.luogu.com.cn/upload/image_hosting/8bu0hhke.png) 图中蓝色部分为积水面积,共有 $6$ 个单位面积积水。

输入输出格式

输入格式


两行,第一行 $n$,表示有 $n$ 个数($3 \le n \le 10000$)。第 $2$ 行连续 $n$ 个数表示依次由正方体叠起的高度,保证首尾为 $0$。

输出格式


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

输入输出样例

输入样例 #1

10
0 1 0 2 1 2 0 0 2 0

输出样例 #1

6