题目描述

  sy被学长们喊去搬砖了，他要将 $N$ 堆砖头摞成一堆。

  他每次可以任选一摞砖头摞到相邻的一摞砖头的上面，这样的操作被称之为“合成”。“合成”一次所花费的体力为你选择摞动的那摞砖头的重量。

  $N$ 摞砖头，每一摞都有它自身的重量。

  现在，sy想知道将这 $N$ 摞砖头“合成”成一摞砖头，所需要花费的最少体力是多少？

输入格式

第一行，输入一个整数 $N(1≤N≤5000)$。

第二行，输入 $N$ 个整数 $w_1, w_2, ..., w_N(1≤w_i≤10^5)$ ，表示第 $1$ 摞砖头至第 $N$ 摞砖头的质量。

输出格式

在一行中输出一个整数，表示将这 $N$ 摞砖头“合成”成一摞砖头所需要花费的最少体力。

样例

5
2 1 2 1 1

5

提示

首先，将第 $2$ 摞砖头摞到第 $3$ 摞砖头上，花费体力 $1$ ，现在的情况为“$2$ $3$ $1$ $1$”；然后此时，将现在的第 $3$ 摞砖头摞到第 $2$ 摞砖头上，花费体力 $1$ ，现在情况“$2$ $4$ $1$”；然后，将现在的第 $3$ 摞砖头摞到第 $2$ 摞砖头上，花费体力 $1$ ，现在情况“$2$ $5$”；最后花费体力 $2$ ，将第一摞砖头摞到第二摞砖头上。总共花费体力 $5$ 。

来源

2022 HGNU-SWUT暑假联合集训