「EZEC-8」Clear Up

题目描述

有一个宽度为 $n$ 的区间,第 $i$ 个位置上如俄罗斯方块一样堆着 $a_i$ 个方块。 你可以选择任何一个位置,花费 $k$ 点能量清除这个位置上的至多 $k$ 个方块,同时在与选定位置相距为 $d$ 的位置清除至多 $\max(k-d,0)$ 个方块,相邻两个位置的距离为 $1$。请注意,**$k$ 必须是正整数。** 请问最少要多少能量才能清空整个区间的所有方块。

输入输出格式

输入格式


输入共两行。 第一行,输入一个整数 $n$。 第二行,输入 $n$ 个整数,第 $i$ 个数为 $a_i$。

输出格式


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

输入输出样例

输入样例 #1

5
1 4 3 4 1

输出样例 #1

5

输入样例 #2

8
1 2 1 0 0 1 2 1

输出样例 #2

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$。