「EZEC-8」Clean Up

有一个宽度为 $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$。