能量项链

题目描述

在Mars星球上，每个Mars人都随身佩戴着一串能量项链。项链上有N颗能量珠，每颗能量珠有头标记与尾标记，标记对应正整数。对于相邻的两颗珠子，前一颗的尾标记一定等于后一颗的头标记，只有满足该条件才能聚合成一颗珠子，同时释放能量。 若前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m × r × n（Mars单位），新产生的珠子的头标记为m，尾标记为n。 项链是环形结构，需要将所有珠子聚合成一颗，不同聚合顺序得到的总能量不同，请设计聚合顺序，使总释放能量最大。

输入描述

第一行是一个正整数N（4 ≤ N ≤ 100），表示项链上珠子的个数。 第二行是N个用空格隔开的正整数，所有数均不超过1000。第i个数为第i颗珠子的头标记（1 ≤ i ≤ N）：

• 当i < N时，第i颗珠子的尾标记等于第i+1颗珠子的头标记；
• 第N颗珠子的尾标记等于第1颗珠子的头标记。 珠子顺序为顺时针排列的环形序列。

输出描述

输出一个正整数E（E ≤ 2.1 × 10^9），表示最优聚合顺序所释放的总能量。

输入样例1

4
2 3 5 10

输出样例1

710

样例1解释

4颗珠子的头、尾标记依次为(2,3)、(3,5)、(5,10)、(10,2)。 最优聚合顺序为：先聚合第4颗和第1颗，释放能量10 × 2 × 3 = 60；再聚合得到的珠子与第2颗，释放能量10 × 3 × 5 = 150；最后聚合得到的珠子与第3颗，释放能量10 × 5 × 10 = 500。总能量为60+150+500=710。