P7594 "EZEC-8" Clean Up

There is an interval of width $n$. At position $i$, there are $a_i$ blocks stacked up like Tetris. You may choose any position and spend $k$ energy to remove at most $k$ blocks at that position. At the same time, at a position whose distance from the chosen position is $d$, you can remove at most $\max(k-d,0)$ blocks, where the distance between two adjacent positions is $1$. Note that **$k$ must be a positive integer.** Find the minimum amount of energy needed to clear all blocks in the entire interval.

The input has two lines. The first line contains an integer $n$. The second line contains $n$ integers, where the $i$-th number is $a_i$.

Output one line with one number, indicating the minimum required energy.

**Sample Explanation** For the first sample, one optimal plan is to choose position $3$ and spend $5$ energy. For the second sample, one optimal plan is to choose position $2$ and spend $2$ energy, then choose position $7$ and spend $2$ energy. ------- **This problem uses bundled testdata.** - 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): No special constraints. For $100\%$ of the testdata, $1 \le n \leq 10^6$, $0 \leq a_i \leq 10^9$. Translated by ChatGPT 5