链接: https://cses.fi/problemset/task/2088

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个包含 $n$ 个数的数组，你的任务是将其划分为 $n$ 个子数组，每个子数组只包含一个元素。

每一步中，你可以选择任意一个子数组，并将其拆分为两个子数组。这一步的代价是被选中子数组内元素之和。

在最优化的情况下，最小的总代价是多少？

输入

第一行有一个整数 $n$：数组大小。数组元素编号为 $1,2,\dots,n$。

第二行有 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组的内容。

输出

输出一个整数：最小总代价。

数据范围

$1 \le n \le 5000$ $1 \le x_i \le 10^9$

样例输入

5
2 7 3 2 5

样例输出

43