题目内容

有一条直线水槽，左右两端始终开口（无挡板，水可从两端流走），水槽中从左到右插入了 $n$ 块竖直挡板，第 $i$ 块挡板高度为 $h[i]$（挡板厚度忽略不计）。

相邻两块挡板之间形成一个槽位（槽底面积为$1$），一共存在$n-1$个槽位。

近期持续下雨，每个槽位都能接收到充足的雨水，直到水面稳定。

对于槽位 $i$（挡板 $i$ 与 $i+1$ 之间）由于槽底面积为 $1$，故槽位的存水量数值等于其水面高度（如果只有一个挡板则无法形成槽位，其存水量为 $0$）。

如下图所示，$5$ 块挡板形成 $4$ 个槽位，以槽位 $3$ 的存水量计算为例，槽位 $3$ 的水面高度受挡板 $2$（高度 $2$）和挡板 $5$（高度 $5$）影响，水面高度为 $2$，故槽位 $3$ 的存水量为 $2$。

输入描述

第一行一个整数 $n$（$1 \le n \le 30000$），表示挡板个数

第二行 $n$ 个整数$h[1],h[2],...,h[n]$（$1 \le h[i] \le 30000$），表示从左往右的每个挡板高度

输出描述

一个整数，输出水槽水面稳定后所有槽位的总存水量

样例1

输入

5
1 2 3 4 5

输出

10

说明

一共$5$个挡板，可以形成$4$个槽位，从左往右每个槽位存水量情况说明如下：

槽位 $1$ 的存水量为 $1$；

槽位 $2$ 的存水量为 $2$；

槽位 $3$ 的存水量为 $3$；

槽位 $4$ 的存水量为 $4$；

总存水量：$1+2+3+4=10$

样例2

输入

6
3 1 2 5 4 5

输出

19

说明

一共$6$个挡板，可以形成$5$个槽位，从左往右每个槽位存水量情况说明如下： 槽位$1$的存水量为$3$； 槽位$2$的存水量为$3$； 槽位$3$的存水量为$3$； 槽位$4$的存水量为$5$； 槽位$5$的存水量为$5$； 总存水量：$3+3+3+5+5=19$