A row of n helium orbs is strung left to right, each labeled with a positive integer. You burst them one at a time in any order. When you burst an orb, you earn coins equal to the product of that orb's label and the labels of its two currently-adjacent orbs (the orbs immediately to its left and right that have not yet been burst). If an orb has no neighbor on some side because that end of the row is reached (all orbs on that side already burst), treat the missing neighbor's label as 1.
After an orb bursts it is removed, so its former neighbors become adjacent. Choose the burst order that maximizes the total coins earned, and report that maximum.
Input format
Line 1: an integer n, the number of orbs.
Line 2: n space-separated positive integers, the orb labels from left to right.
Output format
A single integer: the maximum total coins.
Constraints
- 1 <= n <= 300
- 1 <= each label <= 100