题描述

我想制作一个有 n叶的有序二叉树。该二叉树的成本定义如下。

然而,depth(i),从在该二进制树的左表示第i片叶子的深度。W_i重量是作为输入给出的。请找到最低成本。

输入输出格式

输入格式

输入由标准输入以下列形式给出：

n n n
w1 w_1 w1​ w2 w_2 w2​ ... wn w_n wn​

在第一行中，表示元素数量的整数 n （1≦n≦100,000 ) 第二行显示元素的重量给出了 n个整数。 其中i(1≦i≦n) 表示第i个元素的权重 w_i（1≦w_i≦1,000)

输出格式

输出由标准输出一下格式给出：

输出满足条件的有序二叉树的最低成本。

输入输出样例

暂无测试点

说明

部分测试点

n ≦ 1 0 0 如果你回答的数据集满意， 50分给出。
n ≦ 3,000 n ≦ 3，0 0 0 如果您在回答数据集令人满意的，除了50分中给出。
如果在没有其他约束的情况下更正数据集，则与上述分开 有一点是给出。

输入样例

6
1 2 3 4 9 3

输出样例

53

下图中显示的二叉树是最佳的。

等效于样本输入和输出的二叉树

如果你制作这样的二叉树，那么成本是53。