Nikola's Jumps

Nikola moves along a row of N squares numbered from 1 to N.

Nikola starts on square 1, and his first move must be a jump of length 1 to square 2. After that, every move is controlled by the length of the most recent forward jump.

• When he jumps forward, the jump must be 1 square longer than the most recent forward jump.
• When he jumps backward, the jump must have exactly the same length as the most recent forward jump. A backward jump does not change that reference length.

Each time Nikola lands on a square, he pays that square's entry fee. He does not pay for square 1 at the start, but if he later lands on square 1 again, he must pay its fee then.

Find the minimum total fee Nikola must pay to reach square N.

The first line contains the number of squares N. (2 <= N <= 1000)

The next N lines contain the entry fees for squares 1 through N in order. Each fee is an integer between 1 and 500, inclusive.

Print the minimum total fee Nikola must pay to reach square N.