1130. Minimum Cost Tree From Leaf Values

class Solution:
    def mctFromLeafValues(self, A: List[int]) -> int:
        """" tc O(N) sc O(N)
        get a bigger  than st[-1] value a,  pop() off the smaller value b since we are not going to need it 
        in order to make b's parent value smallest, we need to get b's neighbour small as possible
        
        put product into res 
        
        """
        res = 0
        st = [float('inf')] # add max inf to offset when b need to get its smaller neighour to make smallest product 
        for a in A:
            while st and a > st[-1]:
                b = st.pop()
                res += b*min(a,st[-1])
            st.append(a) 
            # hence st will have decreasing stack 
        while len(st)> 2:
            res += st.pop() * st[-1]
        return res