旧版的石子合并游戏已经为大家所广知了。最近JSOI小组的成员dwyak与好友BenBen聊天时谈起了一种新的石子合并游戏。 BenBen最近被这种石子合并游戏所困惑： 有一排石子，共N堆，每堆分别有s1、s2、s3……sN个。每次可以合并相邻的两堆石子si和sj，合并的代价是si + sj，合并以后得到一堆含si + sj个石子的石堆，放在第i堆石子的位置上。此外与传统石子合并游戏不同的是，每次合并石子之前，可以交换任意两堆石子的位置。 现在，要求你用一定的方法，将N堆石子合并为一堆，使合并总代价最小。 BenBen将这个游戏讲给了dwyak听，dwyak觉得这个游戏挺有趣，于是拿出来与大家分享。

第一行一个整数N（N <= 1 000 000），表示石堆的数量。 第二行N个整数s1、s2、s3……sN，分别表示每个石堆中石子的个数（si <= 1 000 000）。

一个整数，表示最小合并总代价。

3
1 3 2

9