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