There are $n$ dangoes on a line, the $i$-th one on the line has mass $m_i$.

A dango with mass $M_1$ can merge with an adjacent dango with mass $M_2$ by paying a cost of $M_1 + M_2$. They merge to create a combined dango with mass $\max(M_1, M_2)$.

Your task is to determine the minimum cost to merge all dangoes.

Input

The first line contains an integer $n$, the numbers of dangoes.
The second line contains $n$ integers, the $m_i$ representing the mass of the $i$-th dango.

Output

Output an integer, the minimum cost to merge all dangoes.

Constraints

For all testcases, $1 \le n \le 10^6, 1 \le m_i \le 10^9$.
Subtask 1 (10%): $n \le 1000, m_i \le 1000$
Subtask 2 (90%): No additional constraints

Sample Test Cases

Input Output
4
6 9 4 8
44

The minimum cost is $44$ and it can be achieved with the following merges:

  1. Merge 6 and 9 with cost $15$. The array becomes $[9, 4, 8]$
  2. Merge 4 and 8 with cost $12$. The array becomes $[9, 8]$
  3. Merge 9 and 8 with cost $17$. The array becomes $[9]$
$15 + 12 + 17 = 44$.

9
1 9 2 8 3 7 4 6 5
96
Click to copy.

Scoring: Per Subtask
Authored by s17f18
Appeared in 2025 Mini Comp 1