2982 - 屋顶
题目描述
小 A 在奥运会期间，前往巴黎观看奥运会的相关赛事。
在某项体育比赛中，他被场馆的屋顶吸引了，这个屋顶不同于普通的屋顶，在平坦的屋顶上，设计师使用特殊材料制作的边长为 1 米正方体，设计出了各种造型。
由于正方体的高矮不一，下雨时，屋顶会有一定的积水，这些积水会被保留在屋顶，用于场馆内的绿植灌溉。
下图给出了一个宽度为 8 的屋顶的截面图。在截面图中，我们可以看到，白色的方块是特殊材料制作的正方体，蓝色矩形，是下雨后，屋顶上的积水区域。图中积水区域的总面积为 9 平方米。
给定 N 个整数，分别代表宽度为 N 的屋顶，每个位置上正方体的高度，请你编程计算出，在屋顶截面图中，积水区域的最大总面积是多少？
输入
输入两行，第一行输入一个整数 N，屋顶的宽度。
第二行包含 N 个整数，表示每个位置立方体的高度。
输出
一个整数，表示积水区域的最大总面积。
样例
输入
8 2 4 0 1 2 3 0 3
输出
9
输入
7 19 13 3 20 13 8 25
输出
41
输入
11 12 0 30 7 29 17 25 18 9 20 8
输出
55
说明
数据范围
对于 10\% 的数据，满足 1 \le N \le 100，每个位置的立方体高度单调递增。
对于另外 60\% 的数据，满足 1 \le N \le 1000，每个位置的立方体高度没有明显的规律。
对于 100\% 的数据，满足 3 \le n \le 100000 ，每个位置的立方体的高度，均在 [0, 1000] 的范围内。
来源
东方博宜OJ
标签