Description

On the planet Mars, every Martian wears an energy necklace. The necklace has $N$ energy beads. Each bead has a head label and a tail label, both being positive integers. For any two adjacent beads, the tail label of the previous bead must be equal to the head label of the next bead. Only in this way, through the action of a suction cup (an organ used by Martians to absorb energy), can the two beads merge into one, while releasing energy that can be absorbed. If the head and tail labels of the previous bead are $m$ and $r$, and the head and tail labels of the next bead are $r$ and $n$, then the energy released by merging is $m \times r \times n$ (Mars units), and the new bead will have head label $m$ and tail label $n$.

When needed, a Martian uses the suction cup to clamp two adjacent beads and keeps merging to obtain energy until only one bead remains on the necklace. Obviously, different merging orders yield different total energy. Please design a merging order that maximizes the total energy released by the necklace.

For example: let $N = 4$. The head and tail labels of the 4 beads in order are $(2, 3)(3, 5)(5, 10)(10, 2)$. We use the symbol $\oplus$ to denote the merging of two beads, and $(j \oplus k)$ to denote the energy released by merging beads $j$ and $k$. Then the energy released by merging beads $4$ and $1$ is:

$$(4 \oplus 1) = 10 \times 2 \times 3 = 60.$$

One optimal merging order yields the following total energy:

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

Input Format

• The first line contains a positive integer $N$ ($4 \le N \le 100$), the number of beads on the necklace.
• The second line contains $N$ positive integers separated by spaces, each not exceeding $1000$. The $i$-th number is the head label of bead $i$ ($1 \le i \le N$). When $i < N$, the tail label of bead $i$ is equal to the head label of bead $i + 1$. The tail label of bead $N$ is equal to the head label of bead $1$.

To determine the order of the beads, place the necklace flat on a table without crossings, arbitrarily choose the first bead, then determine the remaining beads in the clockwise direction.

Output Format

Output a single integer $E$ ($E \le 2.1 \times 10^9$), the total energy released by an optimal merging order.

4
2 3 5 10

710

Hint

NOIP 2006 Senior Problem 1.

Translated by ChatGPT 5