题目背景

Y 同学正在参与一项城市水利工程的设计。他拿到了一张城市的地形剖面图，图上显示了一系列并排的、宽度相同的建筑物的海拔高度。在雨季来临时，这些建筑物之间会形成洼地，积存雨水。Y 同学需要精确计算出，整个城市剖面图上，总共能积存多少单位的雨水。

题目描述

给定一个由 $N$ 个非负整数组成的序列 height，代表一张地形剖面图。序列中的每个数 height[i] 表示在位置 $i$ 处，有一根宽度为 1 的柱子，其高度为 height[i]。

请计算，当下雨后，这些柱子之间总共能积存多少单位的雨水？

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格隔开的非负整数 height[1], height[2], ..., height[N]。

输出格式

输出一个整数，表示能积存的雨水总量。

样例

样例输入 #1

12
0 1 0 2 1 0 1 3 2 1 2 1

样例输出 #1

6

样例输入 #2

6
4 2 0 3 2 5

样例输出 #2

9

提示

样例 1 解释

数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图。在这种情况下，可以积存 6 个单位的雨水。

数据范围与约定

• $N$ 是 height 数组的长度。
• $1 \le N \le 2 \cdot 10^4$
• $0 \le \text{height}[i] \le 10^5$