Description

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.

Input Format

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 Format

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

5
1 4 3 4 1

5

8
1 2 1 0 0 1 2 1

4

Hint

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