题目描述

有一个宽度为 $n$ 的区间，第 $i$ 个位置上如俄罗斯方块一样堆着 $a_i$ 个方块。

你可以选择任何一个位置，花费 $k$ 点能量清除这个位置上的至多 $k$ 个方块，同时在与选定位置相距为 $d$ 的位置清除至多 $\max(k-d,0)$ 个方块，相邻两个位置的距离为 $1$。请注意，$k$ 必须是正整数。

请问最少要多少能量才能清空整个区间的所有方块。

输入格式

输入共两行。

第一行，输入一个整数 $n$。

第二行，输入 $n$ 个整数，第 $i$ 个数为 $a_i$。

输出格式

输出一行，一个数，表示所需的能量最小值。

5
1 4 3 4 1

5

8
1 2 1 0 0 1 2 1

4

提示

样例解释

对于第一组样例，一种最佳方案是选择位置 $3$ 花费 $5$ 点能量。

对于第二组样例，一种最佳方案是选择位置 $2$ 花费 $2$ 点能量，再选择位置 $7$ 花费 $2$ 点能量。

本题采用捆绑测试。

• Subtask 1（5 points）：$n \leq 2$。
• Subtask 2（20 points）：$n \leq 10^3$，$a_i \neq 0$。
• Subtask 3（20 points）：$a_i \neq 0$。
• Subtask 4（20 points）：$n \leq 10^3$。
• Subtask 5（35 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n \leq 10^6$，$0 \leq a_i \leq 10^9$。