問題文
n 想要创建一个拥有个叶子的有序二叉树。 这个二叉树的成本定义如下。
Σ_{i=1}^{n} w_i × depth(i)
但是,depth(i) 表示在二叉树中从左开始 i 第一个叶子的深度。 w_i 是作为输入给出的权重。 求成本的最小值。
入力
输入是按以下格式从标准输入给出的。
n w_1 w_2 ... w_n
- 1 行表示元素的个数的整数 n (1≦n≦100,000) 。
- 2 行表示元素的权重 n 个整数被给出。在这些中 i (1≦i≦n) 第个元素表示,i 第个元素的权重。 w_i(1≦w_i≦1,000) 。
出力
输出满足条件的有序二叉树的最小成本值。
部分点
针对此问题设置了部分分数。
- n ≦ 100 如果数据集满足条件并且答案正确,50 点。 如果您对除上述数据集之外的所有满足
- n ≦ 3,000 如果数据集满足条件并且答案正确,与上述不同 50 点。 如果您对除上述数据集之外的所有满足
- 如果正确回答了附加的无否定数据集,与上述不同 1 点。 如果您对除上述数据集之外的所有满足
解説
入力例1
6 1 2 3 4 9 3
出力例1
53
以下图所示的二叉树是最适合的。

图1:与示例输入输出相对应的二叉树
如果构造了这样的二叉树,成本为53。