Cheap Tricks

The MAPS executives, the president, vice president, and treasurer, are coordinating an Olympic artistic gymnastics showcase after a workshop. To plan the balance beam routine, they place marks $0, 1, \ldots, n$ along the beam. Mark $0$ is the start, and mark $n$ is the finish.

For every destination mark $i$ with $1 \leq i \leq n$, the judges assign a landing coefficient $c_i$.

A gymnast may move from any mark $j$ to any destination mark $i$. The mark $j$ may be before or after $i$, since a routine is allowed to change direction. Landing at $i$ costs:

Find the minimum total cost needed to reach mark $n$.

Input

The first line contains one integer $n$ ($1 \leq n \leq 10^6$): the number of destination marks.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$), where $c_i$ is the landing coefficient of mark $i$.

Output

Print one integer: the minimum total cost.

Example 1

3
5 4 5

13

Example 2

1
5

5

Example 3

4
1 1 1 1

4

Example 4

5
3 2 3 2 4

12