[Sdoi2008]石子合并

时间限制:3s      空间限制:128MB

题目描述

  在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。
  试设计一个算法,计算出将N堆石子合并成一堆的最小得分。
 


输入格式

  第一行是一个数N
  以下N行每行一个数A,表示石子数目。
 


输出格式

  共一个数,即N堆石子合并成一堆的最小得分。

 


样例输入

4
1
1
1
1
 

样例输出

8
 

提示

对于 100% 的数据,1≤N≤40000
对于 100% 的数据,1≤A≤200


题目来源

没有写明来源