int MonotoneStack(vector<int>& height){
    stack<int>st;
    for(int i = 0; i < height.size(); i++){
        while(!st.empty() && height[st.top()] >= height[i]){
            
        }
        st.push(i);
    }
}

int trap(vector<int>& height) {
        int n = height.size();
        if(n < 3){
            return 0;
        }
        int ans = 0;
        stack<int>st;
        for(int i = 0; i < n; i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int top = st.top();
                st.pop();
                if(st.empty())
                    break;
                int width = i - st.top() - 1;
                int h = min(height[i],height[st.top()]) - height[top];
                ans += width * h;
            }
            st.push(i);
        }
        return ans;
    }

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int>st;
        int ans = 0;
        heights.push_back(0);
        for(int i = 0; i < heights.size(); i++){
            while(!st.empty() && heights[st.top()] >= heights[i]){
                int h = heights[st.top()];
                st.pop();
                if(st.empty()){
                    ans = max(ans, i * h);
                }
                else{
                    ans = max(ans,(i-st.top()-1)*h);
                }
            }
            st.push(i);
        }
        return ans;
    }
};