Today Tomato is going to celebrate year 2015 and for this he is going to valley named DOJO. Tomato live in a valley named DIGO. As we all know Tomato's journey is not so easy because he has to cross a bridge that lie between DOJO and DIGO. The bridge is a straight path consisting of N boxes, numbered 1 to N. Initially Tomato is standing on box 1 and can jump to other boxes. His first jump must be to box number 2.

For each subsequent jump Tomato will follow two rules:

1. If he is making jump in forward direction then his jump must be one box longer than the preceding jump.
2. If he is making jump in backward direction then his jump must be exactly the same length as the preceding jump.

These rules are somewhat weird but Tomato will follow them. Also whenever Tomato jump on a box he has to lose some of his energy as mentioned on the underlying box. Tomato wants to reach box N from box 1 by losing minimum amount of energy. Now determines the minimum total energy that Tomato have to lose to get to box N.

Input

The first line contains the integer N, the number of boxes that make up the bridge. Each of the following N lines contains a positive integer less than 500 indicating amount of energy that Tomato will lose for each box. The energy will be given in order for boxes 1 to N.

2 <= N <= 1000

Output

Output the minimum total energy that Tomato have to lose to get to box N.

Sample

Input:
6
1
2
3
4
5
6

Output:
12

Explanation

After jumping to box 2, Tomato jumps back to box 1. From there he can jump to box 3 and then to 6.