Nikola's Jumps

Time limit1sMemory limit128 MB

Summary

Find the minimum-cost path to square N where forward jumps grow by 1 each time and backward jumps match the last forward jump length.

Level: Medium6 of 10
Topics: Dynamic programming, Graph, Shortest path
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
6
1
2
3
4
5
6
```
Expected output
```
12
```
Example 2
Input
```
8
2
3
4
3
1
6
1
4
```
Expected output
```
14
```