你準備在給定的滑冰賽道上練習滑冰。賽道由起點、$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