题目背景

原题来自 NOIP 2006 提高组。

题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。项链上有 $n$ 颗能量珠。每颗能量珠都有一个头标记和一个尾标记，这些标记对应着正整数。对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

如果前一颗能量珠的头标记为 $m$、尾标记为 $r$，后一颗能量珠的头标记为 $r$、尾标记为 $n$，则这两颗珠子聚合后释放的能量为 $m \times r \times n$，新产生的珠子的头标记为 $m$、尾标记为 $n$。

现在需要不断聚合相邻的两颗珠子，直到项链上只剩下一颗珠子。不同的聚合顺序得到的总能量可能不同。请你设计一种聚合顺序，使项链释放出的总能量最大。

输入格式

第一行包含一个正整数 $n$，表示项链上珠子的数量。

第二行包含 $n$ 个正整数。第 $i$ 个数表示第 $i$ 颗珠子的头标记；当 $i<n$ 时，第 $i$ 颗珠子的尾标记等于第 $i+1$ 颗珠子的头标记；第 $n$ 颗珠子的尾标记等于第 $1$ 颗珠子的头标记。

输出格式

输出一行一个正整数，表示最大释放能量。

4
2 3 5 10

710

样例解释

四颗珠子可看作 $(2,3),(3,5),(5,10),(10,2)$。一种最优聚合顺序释放的总能量为 $10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710$。

数据范围与提示

• $4 \le n \le 100$
• 输入的标记均为不超过 $1000$ 的正整数
• 输出结果不超过 $2.1 \times 10^9$

来源

动态规划，区间动归，NOIP 2006 提高组