Reducing a Sequence

Time limit1sMemory limit128 MB

Summary

Given a sequence, find the minimum total cost of repeatedly merging adjacent elements where cost equals the max of the pair, until one element remains.

Level: Medium4 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

You are given a sequence $a_1, a_2, \dots, a_n$ . The operation $\text{reduce}(i)$ merges the two adjacent elements $a_i$ and $a_{i+1}$ into a single element and places $\max(a_i, a_{i+1})$ in their position. Each time this operation is performed, the length of the sequence decreases by $1$ .

The cost of one $\text{reduce}$ operation is the maximum of the two merged elements, $\max(a_i, a_{i+1})$ . Performing the operation $n-1$ times on a sequence of length $n$ reduces its length to $1$ .

Compute the minimum possible sum of the costs of all $\text{reduce}$ operations needed to reduce the sequence to length $1$ .

Input

The first line contains the length of the sequence $n$ $(1 \le n \le 1{,}000{,}000)$ . Each of the next $n$ lines contains one element $a_i$ of the sequence in order $(0 \le a_i \le 1{,}000{,}000{,}000)$ .

Output

Print the minimum sum of costs required to reduce the sequence to length $1$ .

Examples5

Example 1
Input
```
3
1
2
3
```
Expected output
```
5
```
Example 2
Input
```
1
7
```
Expected output
```
0
```
Example 3
Input
```
2
10
3
```
Expected output
```
10
```
Example 4
Input
```
3
3
2
1
```
Expected output
```
5
```
Example 5
Input
```
3
2
1
3
```
Expected output
```
5
```