Nikola's Jumping Game

Nikola is playing a jumping game on a line of n cells numbered from \(1\) to \(n\). He starts at cell \(1\) and wants to reach cell \(n\). His journey consists of several jumps with the following rules:

• The first jump is forced: he must jump from cell \(1\) to cell \(2\) (jump distance = \(1\)).
• For all subsequent jumps:
• If he jumps toward cell \(n\) (i.e. to the right), his jump distance increases by \(1\) compared to his last jump. That is, if his previous jump was of length \(d\), his new jump will have length \(d+1\).
• If he jumps toward cell \(1\) (i.e. to the left), his jump distance remains exactly the same as his previous jump (i.e. \(d\)).

For example, after the first jump when Nikola is at cell \(2\) (with jump distance \(1\)), he can either jump forward to cell \(4\) (using jump length \(1+1=2\)) or jump backward to cell \(1\) (using jump length \(1\)).

Each time Nikola enters a cell, he must pay an entrance fee associated with that cell. The fee for cell \(i\) is \(a_i\). Nikola wants to reach cell \(n\) while spending as little money as possible. Your task is to compute the minimum total fee he must pay in order to achieve this.

inputFormat

The first line contains an integer \(n\) (\(2 \le n\)).

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) is the fee for entering cell \(i\).

outputFormat

Output a single integer representing the minimum cost to reach cell \(n\) from cell \(1\). If cell \(n\) cannot be reached, output \(-1\).

sample

5
1 2 3 4 5

14