Cutting

Problem Source

Original problem: [NOIP 2004 Advanced Group] Merging Fruits / [USACO06NOV] Fence Repair G (https://www.luogu.com.cn/problem/P1090)

A data-strengthened version requiring an $O(n)$ solution: (https://www.luogu.com.cn/problem/P6033) ($1 \le n \le 10^7$)

Problem Description

There is a wooden board of total length $\sum a_i$ that needs to be cut into $n$ pieces of lengths $a_1, a_2, \dots, a_n$.

Each cut incurs a cost equal to the length of the board being cut.

Find the minimum total cost to cut the board into the $n$ pieces above.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers: $a_1, a_2, \dots, a_n$.

Output Format

Output one positive integer: the minimum cost.

Sample Input

5
5 3 4 4 4

Sample Output

47

Constraints

For all test data: $1 \le n, a_i \le 10^5$.