A canopy is assembled by joining n leaf panels, listed left to right, each with a positive integer value. You build a full binary tree in which these panels are exactly the leaves, in their given left-to-right order. Every internal (non-leaf) node's value is the product of the largest leaf value in its left subtree and the largest leaf value in its right subtree.
Among all such trees, minimize the sum of the values of all internal nodes, and report that minimum sum.
Input format
Line 1: an integer n, the number of leaf panels.
Line 2: n space-separated positive integers, the leaf values from left to right.
Output format
A single integer: the minimum possible sum of all internal-node values (0 when n is 1).
Constraints
- 1 <= n <= 200
- 1 <= each leaf value <= 100