Problem Description

There is a row of $n$ cells, numbered $1 \sim n$. Nikola starts from cell $1$ and wants to reach cell $n$.

His trip consists of several jumps. The first jump can only go to cell $2$. After that, every jump must satisfy the following rules:

• If he jumps in the direction of cell $n$, then each time he must jump a distance that is exactly $1$ cell longer than the previous jump.

• If he jumps in the direction of cell $1$, then each time he must jump a distance exactly the same as the previous jump.

For example, after the first jump (standing on cell $2$), Nikola can choose to jump to $4$ or to $1$.

Each time he enters a cell, Nikola must pay the corresponding entry fee. The fee for cell $i$ is $a_i$. He wants to spend as little money as possible while still being able to reach cell $n$. You need to compute this minimum value.

Input Format

The first line contains an integer $n$, the number of cells.

The next $n$ lines each contain an integer $a_i$, in order, representing the entry fee for cells $1 \sim n$.

Output Format

Output one integer in a single line, the minimum total cost.

Note: the starting cell $1$ is free at the beginning, but if a cell is visited multiple times, you must pay each time you enter it.

6
1
2
3
4
5
6

12

8
2
3
4
3
1
6
1
4

14

Hint

Sample 1 Explanation

In the first sample, Nikola’s route is $1-2-1-3-6$. The total cost is $2+1+3+6=12$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 1000$, $1 \le a_i \le 500$.

Notes

Translated from COCI2007-2008 Regional Competition T2 NIKOLA。

Translated by ChatGPT 5