题目描述

一块试验田被 $n$ 块挡板隔成一排，第 $i$ 块挡板的高度是 $h_i$，挡板厚度忽略不计。

一场大雨过后，所有凹下去的地方都积了水。水不会从最左或最右流出试验田，坑里的水面高度受两侧挡板中较矮的那块限制。

把每块挡板看成宽为 $1$ 的柱子，相邻两块挡板之间的空隙宽为 $1$，可以积水；请你算出整块田里一共积了多少「格」水（一格就是 $1\times 1$ 的面积）。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数 $h_i$。

输出格式

一行一个整数，表示积水总量。

输入输出样例 #1

输入 #1

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

输出 #1

6

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$0\le h_i\le 10^9$。答案用 64 位整数存储不会溢出。