该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目名称

魔法药水

题目描述

小智有 $n$ 颗玻璃球，按顺序排成一排。他准备用魔法药水将这些玻璃球全部粘在一起。

每颗玻璃球有自己的重量，若将两颗玻璃球粘在一起，会合并成一颗新的玻璃球，新球重量是这两颗玻璃球的重量之和。

为保证玻璃球粘贴牢固，粘贴两颗玻璃球所需要的魔法药水与两颗玻璃球的重量乘积成正比，具体认为所需魔法药水等于两颗玻璃球重量的乘积。每次合并，小智只能合并位置相邻的两颗玻璃球，并将合并出的新玻璃球放在原来的位置。

现在，小智想用最少的魔法药水将所有玻璃球粘在一起，请帮助小智计算最少需要多少魔法药水。

输入格式

• 输入的第一行包含一个整数 $n$，表示初始时的玻璃球数量。
• 第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$，依次表示每颗玻璃球的重量。

输出格式

一个整数，表示答案。

输入输出样例 #1

输入 #1

3
3 4 5

输出 #1

47

输入输出样例 #2

输入 #2

8
1 5 2 6 3 7 4 8

输出 #2

546

数据范围

• 对于30%的数据：$1 \leq n \leq 10$，$1 \leq w_i \leq 100$
• 对于60%的数据：$1 \leq n \leq 1000$，$1 \leq w_i \leq 100$
• 对于100%的数据：$1 \leq n \leq 100000$，$1 \leq w_i \leq 100$