题目描述

操场有n堆石子排成一排，每堆石子都有一定的数量，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，合并的花费为这两堆石子的总数。石子经过n-1次合并后成为一堆。

请编写一个程序，读入堆数 n 及每堆的石子数，并计算最小花费。

输入格式

输入第一行一个整数n ，表示有 n 堆石子。

第二行 n 个整数，表示每堆石子的数量。

输出格式

输出共一行表示合并最小花费。

样例

输入

3

输出

2 4 5

17