Description

今天课间的时候，小明同学在学校的操场上发现了n<100堆大小不一的小石子，小明决定将 它们合并成一堆,但现在小明思考着这样一个问题：如何消耗最少的体力，把这n堆小石子合并成一堆？现已知合并所消耗的体力等于每次合并两堆小石子的重量之和。每次合并，他会把其中的两堆小石子合并到一起，n堆小石子经过n-1次合并之后就只剩一堆了。

比如，n=3时表示共有3堆每堆重量分别是2、1、9。一种合并方案是2和9 合并，新堆重量是11，耗费体力为11;接着11与1合并新堆重量是12,耗费体力为12, 因此总消耗体力是11+12=23。另一种方案是先合并1和2，新堆重量是3,耗费体力为3, 接着3和9合并，新堆重量是12，耗费体力为12，因此总消耗体力是3+12=15。可以证明这样合并就是最少耗费体力的方法

Input Format

第一行 一个 整数n，表示有n堆石子

第二行 n个整数，表示每堆的重量

Output Format

3
2 1 9

15

Hint

最大优先队列：priority_queue<int> MaxHeap

最小优先队列：priority_queue<int，vector<int>，greater<int> > MinHeap;

Source