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:
|
||
9 1 9 2 8 3 7 4 6 5 |
96 |
Scoring: Per Subtask
Authored by s17f18
Appeared in 2025 Mini Comp 1