题目描述

在地球上的人类离开之后，只剩下孤独的机器人瓦力。瓦力喜欢把小方块摆成各种形状，而今天它想要建造一座城堡。

瓦力有 N 座塔，第 i 座塔由 A_i 个立方体一层层叠成。机器人只能从塔顶移除立方体，并把它们放到一边。

注意：如果它把某一座塔的所有立方体都移除，那么两边的塔并不会靠拢，中间仍然会留下一个空缺。它的目标是构造出一种称为“城堡”的结构——也就是由若干面“墙”组成、满足特定性质的结构。它想建造一个规模尽可能大的城堡，也就是使用尽可能多立方体的城堡。

城堡必须满足以下条件：

1. 每一面墙由若干连续的塔组成，这些塔的高度先以恰好 1 的幅度递增，再以恰好 1 的幅度递减，从而形成金字塔形。每一面墙最左侧和最右侧的塔高度都必须恰好为 1。
2. 城堡可以由一面或多面墙组成，且这些墙必须首尾相接，中间没有间隔。

例如，若 A = [3, 1, 4, 2, 5, 9, 2]，则一些可能的城堡配置为：

• [1][1][1, 2, 3, 2, 1]：高度和为 1 + 1 + (1 + 2 + 3 + 2 + 1) = 11。
• [1][1, 2, 1][1, 2, 1]：高度和为 1 + (1 + 2 + 1) + (1 + 2 + 1) = 9。
• [1][1][1][1][1][1][1]：高度和为 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7。

第一种配置是最优的。

输入格式

第一行包含整数 N —— 塔的数量（1 ≤ N ≤ 5×10^5）。

第二行包含 N 个整数 A_1, A_2, ..., A_N —— 各座塔的高度（1 ≤ A_i ≤ 10^9）。

输出格式

输出一个整数，表示在满足上述规则的前提下，能够建造出的最大城堡规模（即城堡中各塔高度之和）。

数据范围

• 1 ≤ N ≤ 5 × 10^5
• 1 ≤ A_i ≤ 10^9

子任务

只有在通过某一子任务的全部测试点后，才能获得该子任务的分数。

样例 1

输入

7
3 1 4 2 5 9 2

输出

11

说明

这就是题面中的例子：[1][1][1, 2, 3, 2, 1]。此时高度和最大。

样例 2

输入

11
2 1 2 3 2 1 4 3 6 2 1

输出

19

说明

最优配置为：[1][1, 2, 3, 2, 1][1, 2, 3, 2, 1]。
总和为：

1 + (1 + 2 + 3 + 2 + 1) + (1 + 2 + 3 + 2 + 1) = 19。