描述

Na老师有N张卷子排成一列，第i张卷子有其难度V_i
由于X爷的出现，Na老师需要将这些卷子合并为1张
每次Na老师可以选择相邻两张卷子，消耗两张卷子难度和的体力，得到一张难度为两张卷子难度和的卷子
求Na老师需要消耗的最少体力

输入

第一行：一个整数N
第二行：N个整数V_1、V_2、...、V_N

输出

一行一个整数ANS表示Na老师需要消耗的最少体力

样例1

输入

5
1 2 3 4 5

输出

33

样例2

输入

4
1 3 5 2

输出

22

范围

30% N<=10
60% N<=100
100% 1<=N<=5000 1<=V_i<=10000

限制

1000ms
128M