题目描述

能量球组成的项链。相邻两球可以合并产生新球。合并规则：如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $mrn$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。一条项链怎样合并才能得到最大能量，求最大能量值。

例如：设 $N=4$，珠子的头尾标记分别为 $(2,3) (3,5) (5,10) (10,2)$。

$$[(4\oplus1)\oplus2]\oplus3=10\cdot2\cdot3+10\cdot3\cdot5+10\cdot5\cdot10=710。 $$

输入格式

输入的第一行是一个正整数 $N$，第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$。第 $i$ 个数为第 $i$ 颗珠子的头标记，当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记。第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

输出只有一行，是一个正整数 $E$，为一个最优聚合顺序所释放的总能量。

4
2 3 5 10

710

数据规模与约定

$4\le N\le100$，$E\le2.1\times10^9$。