当前没有测试数据。

题目描述

小 $A$ 在奥运会期间，前往巴黎观看奥运会的相关赛事。

在某项体育比赛中，他被场馆的屋顶吸引了，这个屋顶不同于普通的屋顶，在平坦的屋顶上，设计师使用特殊材料制作的边长为 $1$ 米正方体，设计出了各种造型。

由于正方体的高矮不一，下雨时，屋顶会有一定的积水，这些积水会被保留在屋顶，用于场馆内的绿植灌溉。

下图给出了一个宽度为 $8$ 的屋顶的截面图。在截面图中，我们可以看到，白色的方块是特殊材料制作的正方体，蓝色矩形，是下雨后，屋顶上的积水区域。图中积水区域的总面积为 $9$ 平方米。

给定 $N$ 个整数，分别代表宽度为 $N$ 的屋顶，每个位置上正方体的高度，请你编程计算出，在屋顶截面图中，积水区域的最大总面积是多少？

输入格式

输入两行，第一行输入一个整数 $N$，屋顶的宽度。

第二行包含 $N$ 个整数，表示每个位置立方体的高度。

输出格式

一个整数，表示积水区域的最大总面积。

样例输入 #1

8
2 4 0 1 2 3 0 3

样例输出 #1

9

样例输入 #2

7
19 13 3 20 13 8 25

样例输出 #2

41

样例输入 #3

11
12 0 30 7 29 17 25 18 9 20 8

样例输出 #3

55

数据范围

对于 $10\%$ 的数据，满足 $1 \le N \le 100$，每个位置的立方体高度单调递增。

对于另外 $60\%$ 的数据，满足 $1 \le N \le 1000$，每个位置的立方体高度没有明显的规律。

对于 $100\%$ 的数据，满足 $3 \le n \le 100000$ ，每个位置的立方体的高度，均在 $[0, 1000]$ 的范围内。