题目描述

在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。

输入格式

第一行一个整数 $N$，$N \leq 50000$。

接下来 $N$ 行，第 $i$ 行一个整数 $a_i$，代表第 $i$ 堆石子的石子数，$a_i \leq 1000$。

输出格式

输出将所有石子合并为一堆的最小得分。

4
1
1
1
1

8