Maximum Energy Necklace

On Mars every inhabitant wears a necklace with N energy beads. Each bead is represented as a pair of positive integers: a head label and a tail label. The beads in the necklace obey the property that the tail label of a bead is equal to the head label of its next bead, and the necklace is circular (i.e. the tail label of the last bead equals the head label of the first bead).

Using a special device called a suction cup, a Mars person can merge two adjacent beads. Suppose two adjacent beads are (m, r) and (r, n); merging them releases an energy amount

and the two beads are replaced by a new bead (m, n). This merge operation is repeated until only one bead remains. Since the total released energy depends on the order in which merges are performed, your task is to determine a merge strategy that maximizes the total released energy.

Note: When representing the necklace, you can describe it by a circular sequence of markers p[0], p[1], ..., p[N] where each bead i (for 1 ≤ i ≤ N) is (p[i-1], p[i]) and p[0] = p[N].

Example: For N = 4 and beads (2,3), (3,5), (5,10) and (10,2) (i.e. the marker sequence is 2, 3, 5, 10, 2), one optimal merge order is:

((4 \oplus 1) \oplus 2) \oplus 3

This corresponds to merging beads 4 and 1 first to get energy 10 \times 2 \times 3 = 60, then merging the resulting bead with bead 2 for additional energy 10 \times 3 \times 5 = 150, and finally merging with bead 3 for energy 10 \times 5 \times 10 = 500, making the total energy equal to 710.

inputFormat

The input consists of two lines:

• The first line contains an integer N (the number of beads in the necklace, N ≥ 3).
• The second line contains N+1 space‐separated positive integers representing the marker sequence p[0], p[1], ..., p[N]. It is guaranteed that p[0] = p[N], which represents the circular nature of the necklace.

Example Input:

4
2 3 5 10 2

outputFormat

Output a single integer which is the maximum total energy that can be released by optimally merging the beads.

Example Output:

710

sample

4
2 3 5 10 2

710