645. Minimum Cost Tree From Leaf Values

Given the values of the leaves of a binary tree in left-to-right order, build a tree where each internal node's value is the product of the largest leaf in its left subtree and the largest in its right subtree. Return the minimum possible sum of all internal node values. The input is JSON {arr}.

Input: JSON {arr}.

Output: Integer — the minimum sum of internal node values.

Examples

Input: {"arr":[6,2,4]}
Output: 32
Explanation: An optimal tree gives 32.

Input: {"arr":[4,11]}
Output: 44
Explanation: Only one internal node.

Input: {"arr":[15,13,5,3,15]}
Output: 500
Explanation: Best pairing of leaves.

Constraints

• 2<=n<=40
• 1<=arr[i]<=15

Asked by