Against his own will, Nikola has become the main character in a game. The game is played on a row of ~N~ squares, numbered ~1~ to ~N~. Nikola is initially in square ~1~ and can jump to other squares. Nikola's first jump must be to square ~2~. Each subsequent jump must satisfy two constraints:

• If the jump is in the forward direction, it must be one square longer than the preceding jump.
• If the jump is in the backward direction, it must be exactly the same length as the preceding jump.

For example, after the first jump (when on square ~2~), Nikola can jump back to square ~1~ or forwards to square ~4~.

Every time he enters a square, Nikola must pay an entry fee. Nikola's goal is to get from square ~1~ to square ~N~ as cheaply as possible. Write a program that determines the smallest total cost for Nikola to get to square ~N~.

Input Specification

The first line contains the integer ~N~, ~2 \le N \le 1000~, the number of squares.

Each of the following ~N~ lines contains the entry fee for one square, a positive integer less than ~500~. The entry fees will be given in order for squares ~1~ to ~N~.

Output Specification

Output the smallest total cost for Nikola to get to square ~N~.

Sample Input 1

6
1
2
3
4
5
6

Sample Output 1

12

Sample Input 2

8
2
3
4
3
1
6
1
4

Sample Output 2

14

In the first example, after jumping to square ~2~, Nikola jumps back to square ~1~. From there he can jump to square ~3~ and then to ~6~.