题目内容

有一条水平放置的笔直水槽，其左右两端没有封闭挡板，因此水能够从两端自由流出。水槽内部从左到右依次插有 $n$ 块竖直挡板，第 $i$ 块挡板的高度记作 $h[i]$，挡板厚度忽略不计。

相邻两块挡板之间的区域称为一个槽位，槽位底面积固定为 1。因此当有 $n$ 块挡板时，槽位数量为 $n-1$。

持续降雨后，每个槽位都能获得充足的雨水，直到水面稳定。

求水面稳定后所有槽位的总存水量。

约束条件

• 挡板个数 $n$ 满足 $1 \le n \le 30000$。
• 每块挡板高度 $h[i]$ 满足 $1 \le h[i] \le 30000$。

输入描述

第一行包含一个整数 n，表示挡板个数。

第二行包含 n 个整数，依次为 h[1]、h[2]、...、h[n]，表示从左到右每块挡板的高度。

输出描述

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

样例1

输入

5
2 5 1 3 4

输出

14

说明

如图：

总存水量为 $2+4+4+4=14$。

样例2

输入

4
4 2 3 1

输出

7

说明

如图：

总存水量为 $3+3+1=7$。

样例3

输入

1
5

输出

0

说明

只有一块挡板，挡板数量小于 2，因此不存在任何槽位。

根据题意，总存水量为 0。