#1098. 2-05D.jwp的水果专列

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: lenijwp

题目描述

传说中,神秘的东方古国有一种神秘的水果——长生果,口袋干瘪的jwp看准了这一巨大的商机,砸锅卖铁打算贩卖一大批长生果到资本主义欧气国家。jwp一共从国内 采购调集了n列火车(编号为1,2,...,n)的长生果,它们将在依次进入xjtu货运站进行最后调度后运往“摇钱树下”((#^.^#)),突然jwp发现由于这些长生果的产地不同,它们的新鲜度下降的速度也不同,所以火车运抵欧气国家的顺序决定了jwp的损失,经过计算,jwp发现,每车长生果有一个损失值L,如果这辆车是第i个离开货运站的,这车长生果收益的损失就为L*(i-1),值得注意的是,货运站是一个人字形轨道,意味着这就类似于一个栈,如果1号火车2号火车都相继进入了货运站,1号火车必须在2号火车离开之后才能离开,当然1号火车也可以在2号火车进站之前选择离开。现在jwp希望你能帮助他调度他的n列火车,这可是他成为巨富的唯一机会 了,如果你能帮助jwp,他答应给予你D题的分数作为回报。

输入格式

第一行一个整数 n,表示火车数

下面一行n个整数,表示每个火车的L。

输出格式

一个整数,表示最小的收益损失。

样例

样例输入

5
4 5 3 6 4

样例输出

39

数据范围与提示

1n500 1 \le n \le 500

1L1000 1 \le L \le 1000