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~.
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 the smallest total cost for Nikola to get to square ~N~.
Sample Input 1
6 1 2 3 4 5 6
Sample Output 1
Sample Input 2
8 2 3 4 3 1 6 1 4
Sample Output 2
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~.