1130

class Solution {
public:
    int min(int a, int b){
        return (a < b) ? a:  b;
    }

    int mctFromLeafValues(vector<int>& arr) {
        int res = 0;
        vector<int> stk = {INT_MAX};
        for(int a:arr){
            while(stk.back() <= a){
                int last_max = stk.back();
                stk.pop_back();
                res += last_max * min(stk.back(), a);
            }
            stk.push_back(a);
        }
        for(int i=2; i<stk.size(); i++)
            res += stk[i]*stk[i-1];
        return res;
    }
};