P6507 [CRCI2007-2008] NIKOLA

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.

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 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.**

#### 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](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T2 NIKOLA***。 Translated by ChatGPT 5