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).

Difficulty: interview

Starter code:

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        

Solutions:
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        if not arr: return 0
        
        res = []

        while len(arr) > 1:
            temp_res = []
            temp_res = [arr[i]*arr[i+1] for i in range(len(arr)-1)]
            idx = temp_res.index(min(temp_res))

            res.append(temp_res[idx])
            arr.pop(idx if arr[idx] < arr[idx+1] else idx+1)
                
            # left = arr[0] * arr[1]
            # right = arr[-1] * arr[-2]
            # if left < right:
            #     res.append(left)
            #     arr.pop(1 if arr[1] < arr[0] else 0)
            # elif right < left:
            #     res.append(right)
            #     arr.pop(-2 if arr[-2] < arr[-1] else -1)
            # else:
            #     res.append(left)
            #     if max(arr[0], arr[1]) > max(arr[-1], arr[-2]):
            #         arr.pop(-2 if arr[-2] < arr[-1] else -1)
            #     else:
            #         arr.pop(1 if arr[1] < arr[0] else 0)
        
        return sum(res)

class Solution:
    def mctFromLeafValues(self, A: List[int]) -> int:
        res = 0
        while len(A) > 1:
            i = A.index(min(A))
            neighbors = []
            if i-1 >= 0:
                neighbors.append(A[i-1])
            if i+1 < len(A):
                neighbors.append(A[i+1])
            res += min(neighbors) * A.pop(i)
        return res

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr) > 1:
            mini_idx = arr.index(min(arr))
            if 0 < mini_idx < len(arr) - 1:
                res += min(arr[mini_idx - 1], arr[mini_idx + 1]) * arr[mini_idx]
            else:
                res += arr[1 if mini_idx == 0 else mini_idx - 1] * arr[mini_idx]
            arr.pop(mini_idx)
        return res

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        if len(arr) <= 1: return 0
        min_i = 0
        min_val = arr[0] * arr[1]
        
        for i in range(1, len(arr) - 1):
            cur = arr[i] * arr[i + 1]
            if cur < min_val:
                min_val = cur
                min_i = i
        
        new_arr = arr[:min_i] + [max(arr[min_i], arr[min_i+1])] + arr[min_i+2:]
        return min_val + self.mctFromLeafValues(new_arr)

class Solution:
    def helper(self, arr):
      if not arr:
        pass
      else:
        if len(arr) == 1:
          return 0
        else:
          res = sys.maxsize
          max_ind = arr.index(max(arr))
          for div in range(max_ind, max_ind+2):
            temp_res = 0
            if div == 0 or div == len(arr):
              continue
            temp_res += max(arr[:div])*max(arr[div:])
            temp_res += self.helper(arr[:div])
            temp_res += self.helper(arr[div:])
            res = min(res, temp_res)
            #print (temp_res, div)
          return res
            
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.helper(arr)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr)>1:
            idx = arr.index(min(arr))
            if 0 < idx < len(arr)-1:
                res += min(arr[idx-1],arr[idx+1]) * arr[idx]
                arr = arr[:idx] + arr[idx+1:]
            elif idx == 0:
                res += arr[1] * arr[idx]
                arr = arr[1:]
            else:
                res += arr[-2] * arr[idx]
                arr = arr[:-1]
        return res
                


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        '''
        concept:
            we can do greedy: every time select the two nodes with smallest product as two leafs 
            why greedy works?
            
            we can also maintain a monotone decreasing stack
        '''
        stack = [arr[0]]
        _sum = 0
        for n in arr[1:]:
            while stack and n > stack[-1]:
                n1 = stack.pop()
                
                n2 = n if not stack or n < stack[-1] else stack[-1]
                # print(n1, n2)
                _sum += n1*n2
            stack.append(n)
        # print(stack)
        # print(_sum)
        while len(stack) > 1:
            n1 = stack.pop()
            n2 = stack.pop()
            _sum += n1*n2
            if not stack:
                break
            stack.append(max(n1, n2))
        return _sum


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        
        while (len(arr) > 1):
        
            mid = arr.index(min(arr))
            
            res += min(arr[mid - 1:mid] + arr[mid+1:mid + 2]) * arr.pop(mid)
        
   
        return res

class Solution:
    def mctFromLeafValues(self, arr):
        vals = [[0]*len(arr) for i in range(len(arr))]
        maxes = [[0]*len(arr) for i in range(len(arr))]
        for n in range(1, len(arr)+1):
            for a in range(len(arr) - n + 1):
                b = a + n
                maxes[a][b-1] = max(maxes[a][b-2], arr[b-1])
                if n >= 2:
                    vals[a][b-1] = min((vals[a][i-1] + vals[i][b-1] + (maxes[a][i-1]*maxes[i][b-1]) for i in range(a+1, b)))
        print(vals)
        return vals[0][len(arr)-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[0 for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = (0, arr[i])
        
        for v in range(1,len(arr)):
            for j in range(v, len(arr)):
                i = j - v
                D_i_j = min(dp[i][k][0] + dp[k+1][j][0] + dp[i][k][1] * dp[k+1][j][1] for k in range(i, j))
                M_i_j = max(dp[i][j-1][1], arr[j])
                
                dp[i][j] = (D_i_j, M_i_j)
                
                
        return dp[0][len(arr)-1][0]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n=len(arr)
        max_dp=[[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            temp=arr[i]
            for j in range(i,n):
                temp=max(temp,arr[j])
                max_dp[i][j]=temp
        dp=[[-1 for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i]=0
        for i in range(n-1):
            dp[i][i+1]=arr[i]*arr[i+1]
        for k in range(2,n):
            for i in range(n):
                j=i+k
                if j>=n:
                    break
                dp[i][j]=dp[i][i]+dp[i+1][j]+arr[i]*max_dp[i+1][j]
                for s in range(i+1,j):
                    dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+max_dp[i][s]*max_dp[s+1][j])
        return dp[0][-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[[0,0] for _1 in range(n)] for _2 in range(n)]
        for i in range(n):
            dp[i][i] = [arr[i], 0] # last number and sum
        for diff in range(1,n):
            for i in range(n-diff): #i,i+1,...,i+diff
                temp_min_ = 10**40
                root = None
                for j in range(i,i+diff):
                    sum_ = (dp[i][j][1] + dp[j+1][i+diff][1]) + dp[i][j][0] * dp[j+1][i+diff][0]
                    if sum_ < temp_min_:
                        temp_min_ = sum_
                        root = max(dp[i][j][0], dp[j+1][i+diff][0])
                dp[i][i+diff] = [root, temp_min_]
                        
        return dp[0][-1][1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:        
        # Given an interval of leaves in the range [i, j], we could pick
        # some k, i <= k < j, such that [i, k] are the leaves on the
        # left subtree and [k + 1, j] that of the right subtree
        # For all k: f(i, j) = f(i, k) + f(k + 1, j) + max([i, k]) * max([k+1, j])
        
        n = len(arr)

        # first pre-fill the max(i, j) function
        m = [None] * n
        for i in range(len(m)):
            m[i] = [float('-inf')] * n
            m[i][i] = arr[i]
        for l in range(2, n + 1):
            for i in range(0, n-l+1):
                j = i + l - 1
                mid = (i + j) // 2
                m[i][j] = max(m[i][j], m[i][mid], m[mid+1][j])
           
        # now fill f()
        f = [None] * n
        for i in range(len(f)):
            f[i] = [float('inf')] * n
            f[i][i] = 0
        for l in range(2, n + 1):
            for i in range(0, n-l+1):
                j = i + l - 1
                for k in range(i, j):
                    f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + m[i][k] * m[k+1][j])
        return f[0][n-1]
                                        
                    


class Solution:
    def mctFromLeafValues(self, arr):
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].
        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.
        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.
        We can apply dynamic programming in the following way:
        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

        Improvement 1:
        We calculate the largest leaf value for each possible subtree containing leaf i to j.
        We store those values in the matrix max_leaf_value[i,j].
        We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.
        '''
        maxi = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
        for i in range(len(arr)):
            maxi[i][i] = arr[i]

        for l in range(1, len(arr) - 1):
            for i in range(len(arr) - l):
                j = i + l
                maxi[i][j] = max(maxi[i][j - 1], maxi[i + 1][j])

        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]

        for l in range(1, len(arr)):
            for i in range(0, len(arr) - l):
                j = i + l
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j],
                                   (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + maxi[i][k] *
                                   maxi[k + 1][j])

        return dp[0][len(arr) - 1]

class Solution:
    def mctFromLeafValues(self, arr):
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].
        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.
        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.
        We can apply dynamic programming in the following way:
        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
        '''
        maxi = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
        for i in range(len(arr)):
            maxi[i][i] = arr[i]

        for l in range(1,len(arr)-1):
            for i in range(len(arr)-l):
                j = i + l
                maxi[i][j] = max(maxi[i][j-1], maxi[i+1][j])

        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]

        for l in range(1, len(arr)):
            for i in range(0, len(arr) - l):
                j = i + l
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + maxi[i][k] * maxi[k+1][j])

        return dp[0][len(arr) - 1]
    
        '''
        Improvement 1:
        We calculate the largest leaf value for each possible subtree containing leaf i to j. 
        We store those values in the matrix max_leaf_value[i,j].
        We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.
        '''

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        #the cost of remove a is a * b b >= a. Greedy using the smallest b in the rest to time a to minimize the cost
        while len(arr) > 1:
            i = arr.index(min(arr))
            res += min(arr[i-1:i] + arr[i+1:i+2]) * arr.pop(i)
            
        return res

class Solution:
    def mctFromLeafValues(self, arr):
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].
        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.
        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.
        We can apply dynamic programming in the following way:
        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

        Improvement 1:
        We calculate the largest leaf value for each possible subtree containing leaf i to j.
        We store those values in the matrix maxi[i,j].
        '''
        maxi = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
        for i in range(len(arr)):
            maxi[i][i] = arr[i]

        for l in range(1, len(arr) - 1):
            for i in range(len(arr) - l):
                j = i + l
                maxi[i][j] = max(maxi[i][j - 1], maxi[i + 1][j])

        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]

        for l in range(1, len(arr)):
            for i in range(0, len(arr) - l):
                j = i + l
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j],
                                   (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + maxi[i][k] *
                                   maxi[k + 1][j])

        return dp[0][len(arr) - 1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        N = len(arr)
        dp = [[[0, i] for i in arr]] # length, index, val(0: sum, 1: max)
        for l in range(1, N):
            dp.append([])
            for i in range(N-l):
                dp[l].append([sys.maxsize, 0])
                for x in range(i, i+l):
                    tmp = dp[x-i][i][0]+dp[i+l-x-1][x+1][0]+dp[x-i][i][1]*dp[i+l-x-1][x+1][1]
                    if tmp < dp[l][i][0]:
                        dp[l][i] = [tmp, max(dp[x-i][i][1], dp[i+l-x-1][x+1][1])]
        return dp[-1][0][0]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @lru_cache(None)
        def cached_max(i, j):
            return max(arr[i: j] or [1])
        
        @lru_cache(None)
        def dp(i, j):
            if j - i <= 1:
                return 0
            elif j - i == 2:
                return arr[i] * arr[i + 1]
            return min(dp(i, k) + dp(k, j) + cached_max(i, k) * cached_max(k, j)
                       for k in range(i + 1, j))
        
        return dp(0, len(arr))

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        def compute(arr, lo, hi, dp):
            if dp[lo][hi] != -1:
                return dp[lo][hi]
            if hi == lo:
                dp[lo][hi] = 0, arr[lo]
                return 0, arr[lo]
            if hi == lo + 1:
                dp[lo][hi] = arr[lo]*arr[hi], max(arr[lo], arr[hi])
                return arr[lo]*arr[hi], max(arr[lo], arr[hi])
            
            k = float('inf')
            c = 0
            for i in range(lo, hi):
                #print(\"Cutting at %s\"%i)
                left = compute(arr, lo, i, dp)
                #print(\"left %s,%s\"% left)
                right = compute(arr, i+1, hi, dp)
                #print(\"right %s,%s\"%right)
                t = left[0] + right[0] + left[1]*right[1]
                #print(\"got %s\"% t)
                if t < k:
                    k = t
                    c = max(left[1],right[1])
            dp[lo][hi] = k, c
            return k,c
        
        dp = [[-1]*len(arr) for row in arr]
        
        x= compute(arr, 0, len(arr)-1, dp)
        #print(dp)
        return x[0]


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        def compute(arr, lo, hi, dp):
            if dp[lo][hi] != -1:
                return dp[lo][hi]
            if hi == lo:
                dp[lo][hi] = 0, arr[lo]
                return 0, arr[lo]
            if hi == lo + 1:
                dp[lo][hi] = arr[lo]*arr[hi], max(arr[lo], arr[hi])
                return arr[lo]*arr[hi], max(arr[lo], arr[hi])
            
            k = float('inf')
            c = 0
            for i in range(lo, hi):
                #print(\"Cutting at %s\"%i)
                left = compute(arr, lo, i, dp)
                #print(\"left %s,%s\"% left)
                right = compute(arr, i+1, hi, dp)
                #print(\"right %s,%s\"%right)
                t = left[0] + right[0] + left[1]*right[1]
                #print(\"got %s\"% t)
                if t < k:
                    k = t
                    c = max(left[1],right[1])
            dp[lo][hi] = k, c
            return k,c
        
        dp = [[-1]*len(arr) for row in arr]
        
        x= compute(arr, 0, len(arr)-1, dp)
        print(dp)
        return x[0]


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n=len(arr)
        @lru_cache(None)
        def max_cache(a,b):
            return max(arr[a:b])
        @lru_cache(None)
        def dp(i,j):
            n=j-i
            if n==1: return 0
            if n==2: return arr[i]*arr[j-1]

            
            min_out=2**31-1
            for k in range(i+1,j):
                min_out=min(min_out,max_cache(i,k)*max_cache(k,j)+dp(i,k)+dp(k,j))
        
            return min_out
        return dp(0,n)


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        maximum = [[0 for i in range(len(arr))]for j in range(len(arr))]
        for i in range(len(arr)):
            localMaximum = -math.inf
            for j in range(i,len(arr)):
                localMaximum = max(localMaximum,arr[j])
                maximum[i][j] = localMaximum
        dp = [[math.inf for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = 0
        for length in range(1,len(arr)):
            for left in range(len(arr)-length):
                right = left+length
                if length==1:
                    dp[left][right] = arr[left]*arr[right]
                else:
                    for k in range(left,right):
                        dp[left][right] = min(dp[left][right],dp[left][k]+dp[k+1][right]+(maximum[left][k]*maximum[k+1][right]))
        return dp[0][len(arr)-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        if not arr:
            return 0
        ans = 0
        n = len(arr)
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]
        maxi = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
            maxi[i][i] = arr[i]
            
        for l in range(1, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                for k in range(i,j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + maxi[i][k] * maxi[k+1][j] + dp[k+1][j])
                for k in range(i,j+1):
                    maxi[i][j] = max(maxi[i][j], arr[k])
        return dp[0][-1]



class Solution:
    def __init__(self):
        self.dict = {}
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.mctHelp(arr, 0, len(arr))
        
    def mctHelp(self, arr, a, b):
        if b-a == 1:
            return 0
        if (a,b) not in self.dict:
            low, idx = 2**30, -1
            for i in range(a+1, b):
                res =  self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b)
                if res < low:
                    low = res
                    idx = i
            low += max(arr[a:idx])*max(arr[idx:b])
            self.dict [a,b] = low
        return self.dict [a,b]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        # answer for subarray arr[i: j+1]
        self.cache = {}
        
        
        def dp(i, j):
            if (i,j) not in self.cache:
                if i == j:
                    ret = arr[i], 0
                else:
                    best_p, best_s = 2**32, 2**32
                    for k in range(i,j):

                        l1, s1 = dp(i, k)
                        l2, s2 = dp(k+1, j)

                        if s1 + s2 + l1*l2 < best_s:
                            best_p = max(l1, l2)
                            best_s = s1 + s2 + l1*l2
                        # print('update', i, k, k+1, j, best_p, best_s, s1, s2)

                    ret = best_p, best_s

                self.cache[(i,j)] = ret
            return self.cache[(i,j)]
            
            
        return dp(0, len(arr)-1)[-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # Given an interval of leaves in the range [i, j], we could pick
        # some k, i <= k < j, such that [i, k] are the leaves on the
        # left subtree and [k + 1, j] that of the right subtree
        # For all k: f(i, j) = f(i, k) + f(k + 1, j) + max([i, k]) * max([k+1, j])
        n = len(arr)
        f = [None] * n
        for i in range(len(f)):
            f[i] = [float('inf')] * n
            f[i][i] = 0
        
        m = [None] * n
        for i in range(len(m)):
            m[i] = [float('-inf')] * n
            m[i][i] = arr[i]
        for l in range(2, n + 1):
            for i in range(0, n-l+1):
                j = i + l - 1
                for k in range(i, j):
                    m[i][j] = max(m[i][j], m[i][k], m[k+1][j])
            
        for l in range(2, n + 1):
            for i in range(0, n-l+1):
                j = i + l - 1
                for k in range(i, j):
                    f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + m[i][k] * m[k+1][j])
        return f[0][n-1]
                                        
                    


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        n = len(arr)
        maxs = [[0 if i != j else arr[i] for j in range(n)] for i in range(n)]
        
        for i in range(n-1):
            for j in range(i+1, n):
                for k in range(i, j):
                    maxs[i][j] = max(maxs[i][k], maxs[k+1][j])
                    maxs[j][i] = maxs[i][j]
                    
        print(maxs)
        
        ans = [[0 for j in range(n)] for i in range(n)]
     
        for l in range(1, n):
            for i in range(n-l):
                j = l + i;
                print((i, j))
                ans[i][j] = min(maxs[i][k]*maxs[k+1][j] + ans[i][k] + ans[k+1][j] if j-i>1 else maxs[i][k]*maxs[k+1][j] for k in range(i,j))
                
        print(ans)
                
        return ans[0][n-1]


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        # use dynamic programming 
        # dp[i][j] denotes the cost of constructing a tree from arr[i:j + 1]
        n = len(arr)
        dp = [ [0 for _ in range(n)] for _ in range(n)]
        
        # the cost of constructing a tree from one value is always 0 
        for i in range(n):
            dp[i][i] = 0 
        for i in range(n - 1):
            dp[i][i + 1] = arr[i] * arr[i + 1]
        
        # now work iteratively for subarraies of length: 2, 3, ..., n - 1
        for l in range(2, n + 1):
            # (i, j) is the boundary
            for i in range(n - l):
                j = i + l
                # split the (i, j) array into (i, k) and (k, j) subarraies
                dp[i][j] = float('inf')
                for k in range(i + 1, j + 1):
                    q = dp[i][k - 1] + dp[k][j] + max(arr[i:k]) * max(arr[k: j + 1])
                    if q < dp[i][j]:
                        dp[i][j] = q
                
        return dp[0][-1]
                    
        


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        
        n = len(arr)
        
        mem = {}
        def dp(i, j):
            if i == j:
                    return (0, arr[i])
            if i == j - 1:
                return (arr[i] * arr[j], max(arr[i], arr[j]))
            else:
                if (i, j) in mem:
                    return mem[(i, j)]
                pp = max(arr[i:j + 1])
                minn = 1e10
                for k in range(i, j):
                    l, lm = dp(i, k)
                    r, rm = dp(k + 1, j)
                    minn = min(minn, l + r + lm * rm)
                mem[(i, j)] = (minn, pp)
                return mem[(i, j)]
            
        return dp(0, n - 1)[0]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[0] * len(arr) for i in range(len(arr))]
        
        for i in range(len(arr)-1, -1, -1):
            
            for j in range(i+1, len(arr)):

                if j - i == 1:
                    dp[i][j] = arr[i]*arr[j]
                    continue
                
                m = 2**32
                for k in range(i+1, j+1):
                    s = max(arr[i:k]) * max(arr[k:j+1]) + dp[i][k-1] + dp[k][j]
                    
                    if s < m:
                        m = s
                
                dp[i][j] = m
        return dp[0][-1]
                    
        



class Solution:
    def __init__(self):
        self.vals = None
        
    def mctFromLeafValues(self, arr):
        self.vals = [[0]*len(arr) for i in range(len(arr))]
        for n in range(2, len(arr)+1):
            for a in range(len(arr) - n + 1):
                b = a + n
                self.vals[a][b-1] = min((self.vals[a][i-1] + self.vals[i][b-1] + (max(arr[a:i])*max(arr[i:b]))) for i in range(a+1, b))
        return self.vals[0][len(arr)-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr) > 1:
            mini_idx = arr.index(min(arr))
            if 0 < mini_idx < len(arr) - 1:
                res += min(arr[mini_idx - 1], arr[mini_idx + 1]) * arr[mini_idx]
            else:
                if mini_idx == 0:
                    adj_idx = 1
                else:
                    adj_idx = mini_idx-1
                res += arr[adj_idx] * arr[mini_idx]
            arr.pop(mini_idx)
            #print(arr)
            #print(res)
        return res

class Solution:
  def mctFromLeafValues(self, arr: List[int]) -> int:
    # dp problem
    # arr[i:j] can be split into arr[i:k] and arr[k:j]
    # min_sum of arr[i:j] is min_sum(arr[i:k]) + min_sum(arr[k:j]) + max(arr[i:k]) * max(arr[k:j])
    # max of arr[i:j] is max(max(arr[i:k]), max(arr[k:j]))
    # dp[i][j] maintains min_sum and max value
    if len(arr) == 0:
      return 0
    elif len(arr) == 1:
      return arr[0]
    dp = {}
    for i in range(len(arr)):
      dp[(i, i+1)] = (0, arr[i])
    for length in range(2, len(arr)+1):
      for i in range(len(arr)-length+1):
        # calculate the solution for arr[i: i+length]
        end = i + length
        minSum = float('inf')
        maxLeafValue = float('-inf')
        for k in range(i+1, end):
          # pick [i: k] left tree and [k: end] as right tree
          minSum = min(minSum, dp[(i, k)][0] + dp[(k, end)][0] + dp[(i, k)][1]*dp[(k, end)][1])
          maxLeafValue = max([maxLeafValue, dp[(i, k)][1], dp[(k, end)][1]])
        dp[(i, end)] = (minSum, maxLeafValue)
    
    return dp[(0, len(arr))][0]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # solve(0, n) = min_i(max(a[:i])*max(a[i:])+solve(0, i) + solve(i, n))
        n = len(arr)
        @lru_cache(None)
        def solve(i, j):
            if j - i <= 1:
                return 0
            return min([max(arr[i:k])*max(arr[k:j])+solve(i,k)+solve(k,j)
                        for k in range(i+1,j)])
        return solve(0, n)


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        N = len(arr)
        dp = [[float('inf')]*N for _ in range(N)]
        
        for i in range(N-1, -1, -1):
            for j in range(i, N):
                if i==j: 
                    dp[i][j] = 0
                    continue
                
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+max(arr[i:k+1])*max(arr[k+1:j+1]))
                    
        return dp[0][N-1]

from functools import lru_cache
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        N = len(arr)
        @lru_cache(None)
        def dp(l, r):
            if r - l <= 1:
                return 0
            return min(max(arr[l:m]) * max(arr[m:r]) + dp(l, m) + dp(m, r) for m in range(l + 1, r))
        
        return dp(0, N)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # Given an interval of leaves in the range [i, j], we could pick
        # some k, i <= k < j, such that [i, k] are the leaves on the
        # left subtree and [k + 1, j] that of the right subtree
        # For all k: f(i, j) = f(i, k) + f(k + 1, j) + max([i, k]) * max([k+1, j])
        n = len(arr)
        f = [None] * n
        for i in range(len(f)):
            f[i] = [float('inf')] * n
            f[i][i] = 0
            
        for l in range(2, n + 1):
            for i in range(0, n-l+1):
                j = i + l - 1
                for k in range(i, j):
                    f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + max(arr[i:k+1]) * max(arr[k+1:j+1]))
        return f[0][n-1]
                                        
                    


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0 for j in range(n)] for i in range(n)]
        for i in range(n-2, -1, -1):
            dp[i][i+1] = arr[i]*arr[i+1]
            for j in range(i+2, n):
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+max(arr[i:k+1])*max(arr[k+1:j+1]))
        return dp[0][n-1]
                
                


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[sys.maxsize] * len(arr) for i in range(len(arr))]
        for i in range(0, len(arr)):
            dp[i][i] = 0
        
        for length in range(2, len(arr)+1):
            for i in range(0, len(arr)-length+1):
                j = i+length-1
                for k in range(i, j):
                    temp = max(arr[i:k+1])*max(arr[k+1:j+1])+dp[i][k]+dp[k+1][j]
                    dp[i][j] = min(dp[i][j], temp)
        
        return dp[0][-1]


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[sys.maxsize] * len(arr) for i in range(len(arr))]
        for i in range(0, len(arr)):
            dp[i][i] = 0
            
        
        
        for length in range(2, len(arr)+1):
            for i in range(0, len(arr)-length+1):
                j = i+length-1
                for k in range(i, j):
                    temp = max(arr[i:k+1])*max(arr[k+1:j+1])+dp[i][k]+dp[k+1][j]
                    dp[i][j] = min(dp[i][j], temp)
        
        return dp[0][-1]


class Solution:
    def mctFromLeafValues(self, arr):
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].
        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.
        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.
        We can apply dynamic programming in the following way:
        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
        '''
        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]

        for l in range(1, len(arr)):
            for i in range(0, len(arr) - l):
                j = i + l
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + max(
                        arr[i:k + 1]) * max(arr[k + 1:j + 1]))

        return dp[0][len(arr) - 1]

class Solution:
    def mctFromLeafValues(self, arr):
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].
        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.
        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.
        We can apply dynamic programming in the following way:
        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
        '''
        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]

        for l in range(1, len(arr)):
            for i in range(0, len(arr) - l):
                j = i + l
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + max(
                        arr[i:k + 1]) * max(arr[k + 1:j + 1]))

        return dp[0][len(arr) - 1]
    
    '''
    We calculate the largest leaf value for each possible subtree containing leaf i to j, denoted by max_leaf_value[i,j].
    We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.
    '''

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        '''
        We can use an upper triangular matrix dp[i,j], i<=j, to represent the tree structure.
        Each diagonal element dp[i,i] stores the value of a leaf node arr[i].   
        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.
        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.
        We can apply dynamic programming in the following way:
        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
        '''    
        
        
        dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
        for i in range(len(arr)):
            dp[i][i] = arr[i]
            
        for l in range(1,len(arr)):
            for i in range(0,len(arr)-l):
                j = i + l
                for k in range(i,j):
                    dp[i][j] = min(dp[i][j], (dp[i][k] if i<k else 0) + (dp[k+1][j] if k+1<j else 0) + max(arr[i:k+1]) * max(arr[k+1:j+1]))
                                   
        return dp[0][len(arr)-1]
    
    '''
    We calculate the largest leaf value for each possible subtree containing leaf i to j, denoted by max_leaf_value[i,j].
    We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.
    '''

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        
        def findMax(l, h):
            return max(arr[l:h+1])
        for l in range(1,n):
            for i in range(n-l):
                j = i+l
                for k in range(i, j):
                    tmp = dp[i][k] + dp[k+1][j] + findMax(i,k)* findMax(k+1, j)
                    dp[i][j] = tmp if dp[i][j]==0 else min(dp[i][j], tmp)
                    
        return dp[0][-1]
                    


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n=len(arr)
        dp=[[float('inf') for i in range(n)] for j in range(n)]
        
        
        mem={}
        m=[[-float('inf') for i in range(n)] for j in range(n)]
        
        for i in range(n):
            for j in range(i,n):
                if i==j:
                    m[i][j]=arr[i]
                    continue
                for k in range(i,j+1):
                    m[i][j]=max(m[i][j],arr[k])
                    
        #print(m)
        def rec(left,right):
            if right-left==0:
                return 0
            elif (left,right) in mem:
                return mem[(left,right)]
            else:
                ans=float('inf')
                for k in range(left,right):
                    ans=min(ans,rec(left,k)+rec(k+1,right)+m[left][k]*m[k+1][right])
                mem[(left,right)]=ans
                return ans
        #print(mem)
        return rec(0,n-1)

class Solution:
    def mctFromLeafValues(self, a: List[int]) -> int:
        n = len(a)
        cache =[[[-1,-1]]*n for i in range(n)]
        def dp(i,j):
            if(i==j):
                return [0,a[i]]
            if(cache[i][j] != [-1,-1]):
                return cache[i][j]
            ans = float('inf')
            mx = 0
            for k in range(i,j):
                l = dp(i,k)
                r = dp(k+1,j)
                mx = max(mx,l[1])
                mx = max(mx,r[1])
                ans = min(ans,l[0]+r[0]+l[1]*r[1])
            cache[i][j] = [ans,mx]
            return [ans,mx]
        # print(cache)
        return dp(0,n-1)[0]

class Solution:
    def mctFromLeafValues(self, A: List[int]) -> int:
        '''
        dp(i, j) = dp(i, k) + dp(k, j)
        '''
        @lru_cache(None)
        def dp(i, j):
            if i == j: 
                return 0
            min_cost = float('inf')
            for k in range(i, j):
                min_cost = min(min_cost, dp(i, k) + dp(k+1, j) + max(A[i:k+1]) * max(A[k+1:j+1])) 
            return min_cost
            
        return dp(0, len(A) - 1)

class Solution:
    def ans(self,start,end,arr,dp):
        product=999999999999999
        maxleaf=-1
        if start==end:
            return arr[start],0
        for i in range(start,end):
            if (start,end) in dp:
                return dp[(start,end)]
            a,b=self.ans(start,i,arr,dp)
            c,d=self.ans(i+1,end,arr,dp)
            maxleaf=max(a,c)
            product=min(product,a*c+b+d)
        dp[(start,end)]=(maxleaf,product)
        return maxleaf,product
            
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp={}
        return self.ans(0,len(arr)-1,arr,dp)[1]
            
            


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @lru_cache(maxsize=None)
        def helper(start, end):
            if start >= end:
                return 0
            
            result = float('inf')
            for i in range(start, end):
                rootVal = max(arr[start:i + 1]) * max(arr[i + 1:end + 1])
                result = min(result, rootVal + helper(start, i) + helper(i + 1, end))
            return result
        return helper(0, len(arr) - 1)


class Solution:
    def __init__(self):
        self.vals = None
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self.vals = [[0]*(len(arr)+1) for i in range(len(arr))]
        return self.mctHelp(arr, 0, len(arr))
        
    def mctHelp(self, arr, a, b):
        if b-a == 1:
            return 0
        if self.vals[a][b] == 0:
            low= 2**30
            for i in range(a+1, b):
                res = self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b) + (max(arr[a:i])*max(arr[i:b]))
                if res < low:
                    low = res
            self.vals[a][b] = low
        return self.vals[a][b]

import numpy as np
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        dp = np.diag(arr)

        for distance in range(1,n):
            for i in range(n-distance):
                #calculate dp[i+distance,i] record the maximal number between i,i+distance
                if dp[i+distance-1,i]<= dp[i+distance,i+distance]:
                    dp[i+distance,i] = dp[i+distance,i+distance]
                else: dp[i+distance,i] = dp[i+distance-1,i]

                #calculate dp[i,i+distance] record the smallest sum between i,i+distance
                if distance==1:
                    minvalue = dp[i,i]*dp[i+distance,i+1]
                else:
                    minvalue = dp[i,i]*dp[i+distance,i+1]+dp[i+1,i+distance]
                for j in range(1,distance):
                    #[i,i+j] and [i+j+1,i+distance]
                    if j==distance-1:
                        tempvalue = dp[i+j,i]*dp[i+distance,i+j+1]+dp[i,i+j]
                    else:
                        tempvalue = dp[i+j,i]*dp[i+distance,i+j+1]+dp[i,i+j]+dp[i+j+1,i+distance]
                    if tempvalue<=minvalue:
                        minvalue=tempvalue
                dp[i,i+distance] = minvalue
        return dp[0,n-1]


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        while len(arr) > 1:
            v = min(arr)
            idx = arr.index(v)
            res += min(arr[idx-1:idx] + arr[idx+1:idx+2]) * arr[idx]
            arr.pop(idx)
            
        return res


class Solution:
    def __init__(self):
        self.vals = None
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self.vals = [[0]*len(arr) for i in range(len(arr))]
        return self.mctHelp(arr, 0, len(arr))
        
    def mctHelp(self, arr, a, b):
        if b-a == 1:
            return 0
        if self.vals[a][b-1] == 0:
            low= 2**30
            for i in range(a+1, b):
                res = self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b) + (max(arr[a:i])*max(arr[i:b]))
                if res < low:
                    low = res
            self.vals[a][b-1] = low
        return self.vals[a][b-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        '''
        We can use an upper triangular matrix to represent the tree structure.
        Each diagonal element stores the value of a leaf node.        
        We calculate the largest leaf value for each possible subtree containing leaf i to j, denoted by max_leaf_value[i,j].
        We initialize max_leaf_value[i,i] = arr[i] and max_leaf_value[i,j] = 0 for i!=j.
        We store this value in the corresponding off-diagonal element.
        Let dp[i,j] denote the smallest possible sum of the values of each non-leaf node of the subtree containing leaf i to j.
        We initialize dp[i,j] = inf, i<j.
        We can apply dynamic programming in the following way:
        dp[i,j] = min(d[i,j], d[i,k] + d[k+1,j] + max_leaf_value[i,k] * max_leaf_value[k+1,j]) for k=i,...,j-1
        '''    
        dp = [[float('inf') for i in range(len(arr))] for j in range(len(arr))]
        
        
        for i in range(0, len(arr)):            
            dp[i][i] = 0
        
              
        for l in range(2, len(arr)+1):        
            for i in range(0, len(arr) - l + 1):                                                    
                
                j = i + l - 1
   
                for k in range(i, j):
                                      
                    ans =max(max(arr[i:k+1]), 0) * max(max(arr[k+1:j+1]), 0) + dp[i][k] + dp[k+1][j]                   
                    dp[i][j] = min(dp[i][j], ans)
                
    
        return dp[0][len(arr) - 1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        
        def partition(arr, left, right, cache):
            if (left, right) in cache:
                return cache[(left, right)]
            if left >= right:
                return 0
            result = sys.maxsize
            for k in range(left, right):
                
                root_val = max(arr[left:k+1]) * max(arr[k+1:right+1])
                result = min(result, root_val + partition(arr, left, k, cache) + partition(arr, k+1, right, cache))
            cache[(left, right)] = result
            return result
        
        cache = {}
        partition(arr, 0, n-1, cache)
        return cache[(0, n-1)]

class Solution:
    def max(self, arr, l, r):
        a = max(arr[l:r])
        self.mdp[(l,r)] = a
        return a
    
    def maxDp(self, arr, l , r):
        a = self.mdp.get((l,r), None)
        return self.max(arr, l, r) if a is None else a
    
    def mctFromSubArray(self, arr: List[int], l : int, r : int) -> int:
        if l == r - 1:
            return 0
        if l == r - 2:
            return arr[l] * arr[l + 1]
        return min (self.maxDp(arr, l, k) * self.maxDp(arr, k, r) + self.mctFromSubArrayDp(arr, l, k) + self.mctFromSubArrayDp(arr, k, r) for k in range(l + 1, r))
    
    def mctFromSubArrayDp(self, arr: List[int], l : int, r : int) -> int:
        if (l, r) in self.dp:
            return self.dp[(l, r)]
        ans = self.mctFromSubArray(arr, l, r)
        self.dp[(l, r)] = ans
        return ans
        
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self.dp = {}
        self.mdp = {}
        return self.mctFromSubArrayDp(arr, 0, (len(arr)))
    


class Solution:
    def mctFromSubArray(self, arr: List[int], l : int, r : int) -> int:
        if l == r - 1:
            return 0
        if l == r - 2:
            return arr[l] * arr[l + 1]
        return min (max(arr[l:k]) * max(arr[k: r]) + self.mctFromSubArrayDp(arr, l, k) + self.mctFromSubArrayDp(arr, k, r) for k in range(l + 1, r))
    
    def mctFromSubArrayDp(self, arr: List[int], l : int, r : int) -> int:
        if (l, r) in self.dp:
            return self.dp[(l, r)]
        ans = self.mctFromSubArray(arr, l, r)
        self.dp[(l, r)] = ans
        return ans
        
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self.dp = {}
        return self.mctFromSubArrayDp(arr, 0, (len(arr)))
    



class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.helper(arr, 0, len(arr) - 1, {})
        
    def helper(self, arr, l, r, cache):
        if (l, r) in cache:
            return cache[(l, r)]
        if l >= r:
            return 0
        
        res = float('inf')
        for i in range(l, r):
            rootVal = max(arr[l:i+1]) * max(arr[i+1:r+1])
            res = min(res, rootVal + self.helper(arr, l, i, cache) + self.helper(arr, i + 1, r, cache))
        
        cache[(l, r)] = res
        return res

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self. memo = {}
        def dp(i,j):
            if j<=i:
                return 0
            if (i,j) in self.memo:
                return self.memo[(i,j)]
            res = float('inf')
            for k in range(i,j):
                res = min(res,dp(i,k) + dp(k+1,j) + (max(arr[i:k+1])*max(arr[k+1:j+1])))
            self.memo[(i,j)]=res
            return self.memo[(i,j)]
        return dp(0,len(arr)-1)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
                
        dp = [[float('inf') for i in range(len(arr))] for j in range(len(arr))]
        
        
        for i in range(0, len(arr)):            
            dp[i][i] = 0
        
              
        for l in range(2, len(arr)+1):        
            for i in range(0, len(arr) - l + 1):                                                    
                
                j = i + l - 1
   
                for k in range(i, j):
                                      
                    ans =max(max(arr[i:k+1]), 0) * max(max(arr[k+1:j+1]), 0) + dp[i][k] + dp[k+1][j]                   
                    dp[i][j] = min(dp[i][j], ans)
                
    
        return dp[0][len(arr) - 1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        stack = [float('inf')]
        
        for a in arr:
            while stack[-1] <= a:
                m = stack.pop()
                res += m * min(a,stack[-1])
            stack.append(a)
            
        while len(stack) > 2:
            res += stack.pop()*stack[-1]
            
        return res
                


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.mctHelp(arr, 0, len(arr), {})
        
    def mctHelp(self, arr, a, b, dic):
        if b-a == 1:
            dic[a,b] = 0
        if (a,b) not in dic:
            low = 2**31
            for i in range(a+1, b):
                res = max(arr[a:i])*max(arr[i:b]) + self.mctHelp(arr, a, i, dic) + self.mctHelp(arr, i, b, dic)
                low = min(low, res)
            dic[a,b] = low
        return dic[a,b]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.helper(arr, 0, len(arr) - 1, {})
        
    def helper(self, arr, l, r, cache):
        if (l, r) in cache:
            return cache[(l, r)]
        if l >= r:
            return 0
        
        res = float('inf')
        for i in range(l, r):
            rootVal = max(arr[l:i+1]) * max(arr[i+1:r+1])
            res = min(res, rootVal + self.helper(arr, l, i, cache) + self.helper(arr, i + 1, r, cache))
        
        cache[(l, r)] = res
        return res

class Solution:
    def __init__(self):
        self.dict = {}
    def mctFromLeafValues(self, arr: List[int]) -> int:
        return self.mctHelp(arr, 0, len(arr))
        
    def mctHelp(self, arr, a, b):
        if b-a == 1:
            self.dict[a,b] = 0
        if (a,b) not in self.dict:
            low = 2**31
            for i in range(a+1, b):
                res = max(arr[a:i])*max(arr[i:b]) + self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b)
                low = min(low, res)
            self.dict[a,b] = low
        return self.dict[a,b]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        table = {}
        def dp(i, j):
            if j == i:
                return 0
            if j == i+1:
                return arr[i] * arr[j]
            if (i, j) in table:
                return table[(i, j)]
            res = float('inf')
            for k in range(i, j):
                res = min(res, dp(i, k) + dp(k+1, j) + max(arr[i:k+1]) * max(arr[k+1:j+1]))
            table[(i, j)] = res
            return res
        return dp(0, len(arr)-1)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[float('inf') for i in range(len(arr))] for _ in range(len(arr))]
        
        for i in range(0, len(arr)):
            dp[i][i] = 0
        
        for i in range(0, len(arr)-1):
            dp[i][i+1] = arr[i]*arr[i+1]
            
        for l in range(2, len(arr)+1):
            for i in range(0, len(arr)-l):
                j = i+l
                for k in range(i+1, j+1):
                    dp[i][j] = min(dp[i][j], max(arr[i:k])*max(arr[k:j+1]) + dp[i][k-1] + dp[k][j])
        
        return dp[0][-1]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        table = {}

        def compute(lo, hi):
            if hi - lo == 1:
                return 0

            cost = float('inf')
            for i in range(lo + 1, hi):
                left_key, right_key = f'{lo}-{i}', f'{i}-{hi}'

                if table.get(left_key) is None:
                    table[left_key] = compute(lo, i)
                if table.get(right_key) is None:
                    table[right_key] = compute(i, hi)

                cost = min(cost, table[left_key] + table[right_key] + max(arr[lo: i]) * max(arr[i: hi]))

            return cost

        return compute(0, len(arr))


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        self.memo = {}
        def dp(i, j):
            if i >= j:
                return 0
            if (i,j) not in self.memo:
                res = float('inf')
                for k in range(i, j):
                    res = min(res, dp(i, k) + dp(k+1, j) + max(arr[i:k+1]) * max(arr[k+1:j+1]))
                self.memo[(i,j)] = res
            return self.memo[(i,j)]
        return dp(0, n-1)

import math

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        self.memo = {}
        def dp(i,j):
            if i == j:
                self.memo[(i,j)] = [0, arr[i]]
                return self.memo[(i,j)]
            
            if (i,j) in self.memo:
                return self.memo[(i,j)]
            else:
                local_max = -math.inf
                local_sum = math.inf
                for k in range(i, j):
                    [left_sum, left_max] = dp(i,k)
                    [right_sum, right_max] = dp(k+1,j)
                    local_max = max(local_max, left_max, right_max)
                    local_sum = min(local_sum, left_sum + right_sum + left_max * right_max)
                
                self.memo[(i,j)] = [local_sum, local_max]
                return self.memo[(i,j)]

        return dp(0,len(arr)-1)[0]

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # it's equivalent to merge adjacent pairs one by one
        # every time we merge a pair, they become the bigger one
        # and add the product to the result
        
        def to_remove():
            cur_min = arr[0] * arr[1]
            res = 0 if arr[0] < arr[1] else 1
            for i in range(len(arr) - 1):
                if arr[i] * arr[i + 1] < cur_min:
                    cur_min = arr[i] * arr[i + 1]
                    res = i if arr[i] < arr[i + 1] else i + 1
            return res
        res = 0
        while len(arr) > 1:
            i = to_remove()
            res += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)
        
        return res
        
        res = 0
        while len(arr) > 1:
            i = arr.index(min(arr))
            res += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)
            print(res, arr)
        return res