题目描述

在火星上，每个火星人都随身佩戴着一串能量项链。项链上有 $N$ 颗能量珠，每颗珠子都有头标记和尾标记，相邻两颗珠子的尾标记与头标记相同。

两颗相邻珠子可以聚合为一颗新珠子。若前一颗珠子的头标记为 $m$，公共标记为 $r$，后一颗珠子的尾标记为 $n$，则本次聚合释放的能量为 $m\times r\times n$，新珠子的头、尾标记分别为 $m,n$。

你可以从圆形项链的任意位置开始，不断聚合，直到只剩一颗珠子。请计算能够释放的最大总能量。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $m_1,m_2,\ldots,m_N$。第 $i$ 颗珠子的头标记为 $m_i$，尾标记为 $m_{i+1}$，其中 $m_{N+1}=m_1$。

输出格式

输出一个整数，表示能够释放的最大总能量。

数据范围与约定

$4\le N\le100$，$1\le m_i\le100$。

可见测试数据

输入数据 1

4
2 3 5 10

输出数据 1

710

输入数据 2

5
1 2 3 4 5

输出数据 2

200

输入数据 3

6
3 1 4 1 5 9

输出数据 3

725