题目描述

有一个长度为 $\sum a_i$ 的木板，需要切割成 $n$ 段，每段木板的长度分别为 $a_1, a_2, \dots, a_n$。

每次切割，会产生大小为被切割木板长度的开销。

请你求出将此木板切割成如上 $n$ 段的最小开销。

输入格式

第 $1$ 行一个正整数表示 $n$。

第 $2$ 行包含 $n$ 个正整数，即 $a_1, a_2, \dots, a_n$。

输出格式

输出一个正整数，表示最小开销。

样例输入

5
5 3 4 4 4

样例输出

47

数据范围

对于全部测试数据，满足 $1 \le n, a_i \le 10^5$。

附加说明

原题：[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

需要 $O(n)$ 解法的 数据加强版（$1 \le n \le 10^7$）