你准备在给定的滑冰赛道上练习滑冰。赛道由起点、$N$ 个中间点和终点组成。练习从起点以速度 $0$ 出发，按编号递增的顺序依次经过第 $1$ 到第 $N$ 个中间点，并在以速度 $0$ 到达终点后结束。

每个中间点都有速度限制 $V_i$，因此你必须在移动过程中调整速度，使其不超过下一个要到达的点的速度限制。加速时可以任意提高速度，但减速时只能比上一个经过的点的速度降低 $1$。除起点和终点外，其他位置的速度不能为 $0$。也可以保持速度不变。

练习的成果等于各个点的速度之和，你希望将其最大化。给定滑冰赛道的速度限制，求在该赛道上能够获得的最大练习成果。

例如，若一条赛道有三个中间点，速度限制为 $V=[2,3,1]$，则如果在第 $2$ 个中间点保持速度 $3$，就不可能在第 $3$ 个中间点将速度调整到不超过 $1$。一种可行的练习方式是按 $[2,2,1]$ 调整速度，速度之和为 $2+2+1=5$。其他可行方式还有 $[1,1,1]$ 和 $[1,2,1]$，但它们的速度之和都不超过 $5$。因此，这条赛道上最大的练习成果为 $5$。

数据范围

• 给出的所有数均为整数。
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

子任务

1. 8 分: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 分: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 分: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 分: $N \le 5000$
5. 53 分: 无额外限制。

输入格式

第一行给出 $N$。

第二行依次给出 $V_1,V_2,\ldots,V_N$，以空格分隔。

输出格式

第一行输出答案。

样例

输入格式 1

3
2 3 1

输出格式 1

5

输入格式 2

4
23 7 1 5

输出格式 2

7