LC-chiika

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> hgt[10005];
        for(int i=0; i<n; i++)
        {
            hgt[heights[i]].push_back(i);
        }
        set<pair<int, int>> inter;
        multiset<int> res;
        inter.insert(make_pair(0, n-1)); res.insert(n);
        long long ans = 0;
        for(int i=1; i<10004; i++)
        {
            for(auto stuff : hgt[i-1])
            {
                int ind = stuff;
                pair<int, int> fav = *prev(inter.upper_bound(make_pair(stuff, 1e9)));
                pair<int, int> broken_1 = make_pair(fav.first, stuff-1);
                pair<int, int> broken_2 = make_pair(stuff+1, fav.second);
                res.erase(res.find(fav.second-fav.first+1));
                inter.erase(fav);
                if(broken_1.first<=broken_1.second)
                {
                    inter.insert(broken_1);
                    res.insert(broken_1.second-broken_1.first+1);
                }
                if(broken_2.first<=broken_2.second)
                {
                    inter.insert(broken_2);
                    res.insert(broken_2.second-broken_2.first+1);
                }
            }
            if(inter.empty())
            {
                break;
            }
            ans = max(ans, 1ll*i*(*prev(res.end())));
        }
        return ans;
    }
};