Description

有n堆石子排成一圈，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数 n (1 <= n <= 200)，表示石子堆数； 第二行 n 个整数 a (1 <= a <= 100)，表示每堆石子的个数，这些石子首尾相接排成一圈。

Output

一个整数，表示最小总得分。

Samples

5
7 6 5 7 100

175