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

说明

在Mars星球上，每个Mars人都随身佩带着一串能量项链，在项链上有 $\red{N}$ 颗能量珠。 能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。 如果前一颗能量珠的头标记为$\red{m}$，尾标记为$\red{r}$，后一颗能量珠的头标记为 $\red{r}$，尾标记为 $\red{n}$，则聚合后释放的能量为 $\red{m*r*n}$（Mars单位），新产生的珠子的头标记为 $\red{m}$，尾标记为 $\red{n}$。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设$\red{N=4}$，$\red{4}$颗珠子的头标记与尾标记依次为$\red{(2，3) (3，5) (5，10) (10，2)}$。

我们用记号$\red{⊕}$表示两颗珠子的聚合操作，$\red{(j⊕k)}$表示第 $\red{j，k}$ 两颗珠子聚合后所释放的能量。

则第$\red{4、1}$两颗珠子聚合后释放的能量为：$\red{(4⊕1)=10*2*3=60}$。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为$\red{ ((4⊕1)⊕2)⊕3）= 10*2*3+10*3*5+10*5*10=710}$。

输入格式

输入的第一行是一个正整数 $\red{N}$，表示项链上珠子的个数。

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

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

输出格式

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

样例

输入数据

4
2 3 5 10

输出数据

710

提示

$\red{4\ ≤\ N\ ≤\ 100}$,

$\red{1\ ≤\ E\ ≤ \ 2.1\ ∗ \ 10^9}$