题目描述

屋顶的截面由 $N$ 根宽度均为 $1$ 的柱子组成，第 $i$ 根柱子的高度为 $H_i$。下雨后，水会积在柱子之间，屋顶两端以外的水会流走。

请计算屋顶截面中最多能够积存多少单位面积的水。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $H_1,H_2,\ldots,H_N$。

输出格式

输出一个整数，表示积水区域的总面积。

样例

8
2 4 0 1 2 3 0 3

9

数据范围与提示

• 对于 $10\%$ 的数据，$1 \le N \le 100$，柱子高度单调不减
• 对于另外 $60\%$ 的数据，$1 \le N \le 1000$
• 对于 $100\%$ 的数据，$3 \le N \le 10^5$，$0 \le H_i \le 1000$