Bessie’s Shockwave Brick Breaking

Bessie is experimenting with a powerful hoof implant that produces huge shockwaves. In front of her are \(N\) bricks arranged in a row (with \(2\le N\le 10^5\)). The \(i\)th brick requires at least \(p_i\) units of force to break (\(0\le p_i\le 10^{18}\), for \(i=0,1,\dots,N-1\)).

When Bessie strikes a brick at index \(x\) (where \(0\le x\le N-1\)), note that her implant does not apply any force to the brick she directly hits. Instead, every brick at index \(i\) (\(0\le i\le N-1\)) receives an impact of \(|i-x|\) units of force. These forces accumulate: if a brick receives, say, two hits that each provide 2 units of force, then it has received a total of 4 units of force.

Determine the minimum number of hits required for Bessie to break all the bricks.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains the integer \(N\), the number of bricks.

The second line contains \(N\) space‐separated integers \(p_0, p_1, \dots, p_{N-1}\), where \(p_i\) is the force required to break the \(i\)th brick.

outputFormat

Output a single integer: the minimum number of hits needed to break all the bricks.

sample

2
0 0

0