Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.  (Recall that a node is a leaf if and only if it has 0 children.)
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node.  It is guaranteed this sum fits into a 32-bit integer.
 
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

 
Constraints:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "class Solution:\n    def mctFromLeafValues(self, arr):\n        '''\n        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.\n        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].\n        Each off-diagonal element dp[i,j], i<j, denotes the smallest possible sum of the values of each non-leaf node of the subtree containing leaf i to j.\n        We initialize dp[i,j] = inf for i<j-1; dp[i,j] = arr[i] * arr[j] for i=j-1; dp[i,j] = arr[i] for i=j.\n        We can apply dynamic programming in the following way:\n        dp[i,j] = min(d[i,j], (d[i,k] if i<k else 0) + (d[k+1,j] if k+1<j else 0) + max[i,k] * max[k+1,j]) for k=i,...,j-1, j>i\n\n        Improvement 1:\n        We calculate the largest leaf value for each possible subtree containing leaf i to j.\n        We store those values in the matrix max_leaf_value[i,j].\n        We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.\n        '''\n        maxi = [[0 for _ in range(len(arr))] for _ in range(len(arr))]\n        for i in range(len(arr)):\n            maxi[i][i] = arr[i]\n\n        for l in range(1, len(arr) - 1):\n            for i in range(len(arr) - l):\n                j = i + l\n                maxi[i][j] = max(maxi[i][j - 1], maxi[i + 1][j])\n\n        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]\n        for i in range(len(arr)):\n            dp[i][i] = arr[i]\n\n        for l in range(1, len(arr)):\n            for i in range(0, len(arr) - l):\n                j = i + l\n                for k in range(i, j):\n                    dp[i][j] = min(dp[i][j],\n                                   (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + maxi[i][k] *\n                                   maxi[k + 1][j])\n\n        return dp[0][len(arr) - 1]"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'mctFromLeafValues'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 7832