Description

{{He measured the fence and found that he needs $n$ wooden boards, each with an integer length $l_i$. So, he bought one board long enough, whose length equals the sum of the required $n$ boards, and decided to cut it into the $n$ boards he needs (Ruirui produces no sawdust when cutting, so ignore any loss of length).

Ruirui uses a special method: cutting a board of length $x$ into two pieces costs $x$ units of energy. He has endless energy, but in the spirit of saving energy, he wants to minimize the total energy used. Clearly, there must be $(n-1)$ cuts in total. The question is: how should he cut each time? Please compute the minimum possible total energy.}}

Input Format

{{The first line contains an integer $n$, the number of boards needed.

Lines $2$ to $n+1$ each contain one integer. The integer on line $(i+1)$ is $l_i$, the length of the $i$-th board.}}

Output Format

{{Output a single integer, the minimum total energy required.}}

3
8
5
8

34

Hint

{{Explanation for Sample 1

Cut the board of length $21$ first into lengths $8$ and $13$, costing $21$ units of energy. Then cut the board of length $13$ into $5$ and $8$, costing $13$ units of energy. The total cost is $34$ units, which is minimal.

Constraints

• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2 \times 10^4$, $1 \le l_i \le 5 \times 10^4$.}}

Translated by ChatGPT 5