Clear the Blocks with Tetris-like Moves

We are given an interval of width (n) where at position (i) there are (a_i) blocks stacked like Tetris blocks. You can perform the following operation: choose any position and spend a positive integer (k) units of energy to remove up to (k) blocks at the selected position. In addition, at any position at distance (d) from the chosen position (with adjacent positions having distance 1), you can remove up to (\max(k-d,0)) blocks. What is the minimum total energy required to clear all the blocks in the entire interval?

inputFormat

The first line contains an integer (n), the width of the interval. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n), where (a_i) is the number of blocks at the (i)th position.

outputFormat

Output a single integer representing the minimum total energy required to clear all blocks.

sample

4
0 0 0 0

0