#P1318. 积水

积水

题目背景

小B家的院子里有很多的坑,一到下雨天就会积水,勤俭持家的小B想收集这些水来冲马桶,所以他想知道院子里一共能积多少的水。

题目介绍

一组正整数,分别表示地面的高度(如下图,0x50000 \le x \le 5000)。找出所有可能积水的地方(图中蓝色部分),统计它们可能积水的面积总和(计算的是图中的横截面积。一个立方体的位置,为一个单位面积)。

如图:地面高度变化为 0 1 0 2 1 2 0 0 2 0

图中蓝色部分为积水面积,共有 66 个单位面积积水。

输入格式

两行,第一行 nn,表示有 nn 个数(3n100003 \le n \le 10000)。第 22 行连续 nn 个数表示高度,保证首尾为 00

输出格式

一个数,可能积水的面积。

10
0 1 0 2 1 2 0 0 2 0
6