Baltic Olympiad in Informatics: 2007 Day 2, Problem 3

We are given a sequence $a_1,\dots ,a_n$. We can manipulate this sequence using the operation reduce(i), which replaces elements $a_i$ and $a_{i+1}$ with a single element $max(a_i,a_{i+1})$, resulting in a new shorter sequence. The cost of this operation is $max(a_i,a_{i+1})$. After $n-1$ reduce operations, we obtain a sequence of length $1$. Our task is to compute the cost of the optimal reducing scheme, i.e. the sequence of reduce operations with minimal cost leading to a sequence of length $1$.

Constraints

$1\le n\le {10}^6$

$0\le a_i\le {10}^9$

Subtask 1 [30%]

$1\le n\le 500$

Subtask 2 [20%]

$1\le n\le 2\times {10}^4$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line of input contains an integer $n$, the length of the sequence. The following $n$ lines contain one integer $a_i$, the elements of the sequence.

Output Specification

Output the minimal cost of reducing the sequence to a single element.

Sample Input

3
1
2
3

Sample Output

5

Explanation for Sample Output

The optimal way to reduce the array to one element has a cost of $max(1,2)+max(2,3)$:

• [1, 2, 3] → [2, 3]
• [2, 3] → [3]