题目描述

在 ASC 智能车实验室，调试时经常需要整合各类传感器的采样数据块 —— 就像处理一堆堆 “果子” 似的。实验室规定：每次可以把两个数据块合并成一个，消耗的算力等于两块数据的大小之和。要把 n 个初始数据块最终整合成一个，总共得合并 n-1 次，总算力消耗就是每次合并的算力之和。 为了让智能车的主控芯片更高效运行（毕竟算力得省着用），得找出最优的合并顺序，让总算力消耗最少。已知每个基础数据单元的大小固定为 1，现在给出数据块的种类数和每种的数量，你来算算最小的总算力消耗吧～ 比如有 3 个数据块，大小依次为 1、2、9。先把 1 和 2 合并成大小 3 的新块，消耗算力 3；再把这个新块和 9 合并成 12，消耗 12。总共消耗 3+12=15，这就是最优方案啦。

输入格式

两行，第一行是一个整数 n（1≤n≤30000），表示数据块的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数 ai（1≤ai≤20000）是第 i 种数据块的数量。

输出格式

一行，只包含一个整数，也就是最小的总算力消耗值。输入数据保证这个值小于 2³¹。

样例

1 
5

0