Description

Original source: NOIP 2006

On the planet Mars, every Martian wears a string of energy necklaces. The necklace has $N$ energy beads. Each bead has a head mark and a tail mark, which correspond to some positive integers. Moreover, for any two adjacent beads, the tail mark of the previous bead must equal the head mark of the next bead. Only under this condition can the two beads be merged into one through the action of a sucker—the organ Martians use to absorb energy. If the head mark of one bead is $m$, the tail mark is $r$, and the head mark of the next bead is $r$ with a tail mark of $n$, then merging them releases $m\times r\times n$ units of Mars energy. The new bead will have a head mark of $m$ and a tail mark of $n$.

When needed, Martians use suckers to clamp two adjacent beads, merging them to obtain energy until only one bead remains on the necklace. Clearly, different merging orders yield different total energy outputs. Design a merging sequence that maximizes the total energy released from the necklace.

For example, let $N=4$, with the four beads' head and tail marks as $(2,3),(3,5),(5,10),(10,2)$. We denote the merging operation of two beads by $\bigotimes$, where $(j\bigotimes k)$ represents the energy released by merging beads $j$ and $k$. The energy released by merging the $4$th and $1$st beads is $(4\bigotimes 1)=10\times 2\times 3=60$. An optimal merging sequence for this necklace releases a total energy of $(((4\bigotimes 1)\bigotimes 2)\bigotimes 3)=$ $10\times 2\times 3+10\times 3\times 5+10\times 5\times 10=710$.

Now, given a necklace with $n$ beads, where adjacent beads can be merged into one, each merge releases a certain amount of energy, and different merges release different amounts of energy, what is the optimal merging order to maximize the total energy released?

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers not exceeding $1000$, where the $i$-th $(1\le i \le n)$ number is the head mark of the $i$-th bead. When $i\neq n$, the tail mark of the $i$-th bead equals the head mark of the $(i+1)$-th bead. When $i=n$, the tail mark of the $i$-th bead equals the head mark of the $1$st bead.

As for the order of the beads, you can determine it as follows: place the necklace on a flat surface without any crossings, randomly designate one bead as the first, and determine the order of the other beads clockwise.

Output Format

Output only one line, a positive integer not exceeding $2.1\times 10^9$, representing the maximum total energy released by the optimal merging sequence.

Sample 1

4
2 3 5 10

710

Data Range and Hints

For $100\%$ of the data, $4\le n \le 100$.