题目描述

有$N$个人参加选秀。

一开始，这$N$个人按照从$1$到$N$的顺序依次站好了，第$i$个人的情绪每一个回合会积攒$a_i$（情绪越大，上台表演完以后的自述环节就把自己讲的身世越凄惨，观众就越爱看）。

上述内容的简单描述是：每回合会有一个人上台表演，那么这一回合，还没表演的其他人就会各自增加$a_i$的情绪，请注意每个人的$a_i$不一定相同。

你作为编导，可以用一个栈来调整他们的出场顺序。

确切的说：你可以让当前队首的那个人进栈，或者是让当前栈顶的人去表演。

但你很坏，你不希望他们在台上哭哭啼啼的，所以，你希望总的凄惨值越小越好。

问：最小值是多少。

输入格式

第一行$N(1\leq N\leq 500)$。

第二行$N$个数字表示$a_i(1\leq a_i \leq 10^5)$。

输出格式

一个数字表示答案。

样例输入1

3
1 2 3

样例输出1

4

样例解释

一开始三个人依次进栈，然后$3$第一回合表演，$2$第二回合表演，$1$第三回合表演，总代价$2+1\times 2=4$