3923 - 美丽塔 Ⅱ
时间限制 : 1 秒
内存限制 : 128 MB
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
1 \leq heights[i] \leq maxHeights[i]
对于所有 0 < j \leq i ，都有 heights[j - 1] \leq heights[j]
对于所有 i \leq k < n - 1 ，都有 heights[k + 1] \leq heights[k]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
输入
第一行一个整数 n
第2行一共n个整数，maxHeights[i]
输出
输出仅一个数，即所有塔高度的和
样例
输入
5 5 3 4 1 1
输出
13
输入
6 6 5 3 9 2 7
输出
22
输入
6 3 2 5 5 2 3
输出
18
提示
n \leq 5×10^5 , 0 < maxHeights[i] \leq 10^9
来源
leetcode