锻合晶核

裁断的信息流在屏幕上排列整齐，但Zero的核心还需要一样东西——能源。

"晶核。"CC说，"废墟里有散落的能量晶核，小的，碎的。要锻合成大的。"

"锻合？"Echo问。

"对。"CC说，"像打铁——两块小的并成一块大的。每次锻合要消耗能源，消耗的量和两块晶核的大小有关。"

"多少？"

"和两块晶核的大小之和一样。"你说，"比如3和5锻合成8，消耗8点能源。"

"那咋合最省？"

"Garsia-Wachs。"你说，"每次找最小的相邻对，先合。这样总消耗最小。"

"最小相邻对？"

"对。"你说，"设三堆晶核：3,5,2。先合3和5？消耗8。变成8,2。再合8和2，消耗10。总消耗18。"

"但如果先合5和2。"Echo说，"消耗7。变成3,7。再合3和7，消耗10。总消耗17。"

"更小。"

"对。"你说，"所以不是任意合，要找最优顺序。"

你开始写。Garsia-Wachs算法——维护一个序列，每次找最小的相邻对，合并，插入到合适的位置。

"第一步。"你说，"3,5,2。最小相邻对是5和2，合为7。"

"序列变成3,7。"

"第二步。"你说，"3和7，合为10。"

"总消耗7+10=17。"

"验证一下。"你说，"3,5,2。如果按顺序合3和5，再合8和2，总消耗8+10=18。确实更大。"

"那就按Garsia-Wachs。"

"对。"

CC从废墟里拖出一箱碎晶核——蓝色的，发光的，像星星的碎片。

"我来搬。"她说，"你来算。Echo来盯。"

"盯啥？"

"盯晶核的辐射。"Echo说，"有些碎了太久，不稳定。锻合的时候可能炸。"

"会炸？"

"会。"Echo说，"但我能预判——0.3秒前给出警报。"

"0.3秒够干啥？"

"够CC躲开。"你说，"她反应快。"

"那是。"CC把一块晶核扔进锻合炉，"我能打。"

锻合炉开始运转——蓝光闪烁，嗡嗡作响。你们三个人围在炉边：CC添料，你算顺序，Echo盯辐射。

"第一块。"你说，"3和2。"

"好。"CC把两块晶核推进炉。

"消耗5。"你说，"新晶核5。"

"第二块。"你说，"5和5。"

"好。"

"消耗10。"你说，"新晶核10。"

"第三块。"你说，"10和8。"

"消耗18。"你说，"总消耗5+10+18=33。"

"够用了？"

"够重启一个子系统。"你说，"我们要33块这样的大晶核，才能重启全部。"

"那就继续锻。"CC说，"锻到够为止。"

Echo的投影在锻合炉的蓝光中，第一次有了温度——不是屏幕的温度，是某种更接近"在场"的东西。

"我能感受到热。"她说。

"那是炉子的热。"

"不。"她说，"是你们的热。"

题目描述

给定$n$堆晶核，第$i$堆大小为$a_i$。每次可以把相邻的两堆合并为一堆，代价为两堆大小之和。求将所有晶核合并为一堆的最小总代价。

输入格式

$n$。然后$n$个整数。

输出格式

最小总代价。

输入样例

3
1 2 3

输出样例

9

提示

• Garsia-Wachs算法。
• 每次找最小的相邻对合并，但插入位置要保证最优性。
• 可以用平衡树或链表维护，时间复杂度$O(n\log n)$或$O(n^2)$。
• 也可以区间DP：$dp[i][j]=\min(dp[i][k]+dp[k+1][j]+sum(i,j))$，但$O(n^3)$需要优化。