Minimum Cost Sequence Reduction

Given a sequence of integers (a_1, a_2, \ldots, a_n), you are allowed to perform the following operation until only one number remains:

$$\text{reduce}(i): \quad \text{Replace } a_i \text{ and } a_{i+1} \text{ with } \max(a_i, a_{i+1}), \quad \text{with cost } \max(a_i, a_{i+1}). $$

After performing exactly (n-1) operations the sequence becomes a single number. Your task is to determine the minimum total cost needed to reduce the sequence to a single element.

Observation: In any optimal strategy, each operation removes the smallest available element by merging it with its adjacent element having the smaller of its two neighbors (if both exist) or the only neighbor if it is at one of the ends. Thus, one can use a greedy strategy: repeatedly remove the smallest element, adding cost (=\min(\text{left neighbor}, \text{right neighbor})) if both neighbors exist (or the only neighbor if at an end), until one element remains.

inputFormat

The first line of input contains a single integer (n) (the length of the sequence). The second line contains (n) space-separated integers representing the sequence (a_1, a_2, \ldots, a_n).

outputFormat

Output a single integer: the minimum total cost to reduce the sequence to just one element.

sample

2
3 4

4