最小合并代价

难度：T2

【知识点：优先队列接口】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

有 $n$ 段材料。每次可以任意选择两段合成一段，新长度为两段长度之和，费用也等于新长度。持续合并到只剩一段，求总费用的最小值。只有一段时不需要合并，费用为 $0$。

输入格式

输入$n$及$n$个非负长度。每次选两段合成一段，新长度为两者之和，本次费用为新长度；直至只剩一段。

输出格式

输出最小总费用；只有一段时费用为$0$。

数据范围

$1\le n\le 100000$，长度≤$1000000000$。

样例输入

1
0

样例输出

0

样例输入 2

4
1 2 3 4

样例输出 2

19

样例说明 2

一种最优过程是合并 $1,2$，再合并两段长度 $3$，最后合并 $6,4$，费用为 $3+6+10=19$。