最优合并

题目描述

有 n 堆椰子，每堆有一定数量。每次可以选择两堆合并，合并代价等于两堆数量之和。请问把所有椰子合并成一堆的最小总代价是多少？

输入格式

第一行一个整数 n。第二行 n 个正整数。

输出格式

输出一个整数，表示最小总代价。

样例

输入样例 1

4
1 2 3 4

输出样例 1

19

数据范围与提示

1≤n≤100000，椰子数量为正整数，答案可能较大，请使用 long long。