题目描述

有一串由 $N$ 颗珠子组成的环形珠串，每颗珠子上有一个头标记和一个尾标记，均为正整数。对于相邻的两颗珠子，前一颗的尾标记等于后一颗的头标记（环形首尾相接）。

可以对相邻的两颗珠子执行合并操作：若前一颗珠子的头标记为 $m$、尾标记为 $r$，后一颗珠子的头标记为 $r$、尾标记为 $n$，则合并后释放能量 $m \times r \times n$，并产生一颗新的珠子，其头标记为 $m$、尾标记为 $n$。

反复执行合并操作，直到整串珠子只剩一颗为止。不同的合并顺序会产生不同的总能量，请找到使总能量最大的合并顺序。

例如：$N = 4$，四颗珠子的头尾标记依次为 $(2,3),\;(3,5),\;(5,10),\;(10,2)$。用 $(j \oplus k)$ 表示合并第 $j$、$k$ 颗珠子释放的能量，则一种最优方案为：

$(((4 \oplus 1) \oplus 2) \oplus 3) = 10 \times 2 \times 3 + 10 \times 3 \times 5 + 10 \times 5 \times 10 = 710$。

输入格式

第一行一个正整数 $N$（$4 \le N \le 100$），表示珠子数量。

第二行 $N$ 个用空格隔开的正整数，每个数不超过 $1000$。第 $i$ 个数为第 $i$ 颗珠子的头标记。当 $i \lt N$ 时，第 $i$ 颗珠子的尾标记等于第 $i+1$ 颗珠子的头标记；第 $N$ 颗珠子的尾标记等于第 $1$ 颗珠子的头标记。

输出格式

输出一个正整数 $E$（$E \le 2.1 \times 10^9$），为最优合并顺序释放的总能量。

样例

4
2 3 5 10

710