class Solution {
public:
    vector<int> bit;
    void up(int idx,int val)
    {
        for(int i=idx;i<bit.size();i+=(i&-i)) bit[i] = min(bit[i],val);
    }
    int read(int idx)
    {
        int res = bit.size();
        for(int i=idx;i>0;i-=(i&-i)) res = min(res,bit[i]);
        return res;
    }
    int maxArea(vector<int>& height) {
        bit.assign(height.size()+7,height.size()+7);

        vector<int>tmp = height;
        sort(tmp.begin(),tmp.end());
        int sz = unique(tmp.begin(),tmp.end()) - tmp.begin();

        int res = 0;

        for(int i=0;i<height.size();i++)
        {
            int mpv = lower_bound(tmp.begin(),tmp.begin()+sz,height[i]) - tmp.begin() + 1;
            int rev_id = height.size()  - mpv + 1;
            int pos = read(rev_id);
            if(pos<i)  res = max(res,(i - pos) * height[i]);
            up(rev_id,i);
        }


        bit.assign(height.size()+7,height.size()+7);
        reverse(height.begin(),height.end());

        for(int i=0;i<height.size();i++)
        {
            int mpv = lower_bound(tmp.begin(),tmp.begin()+sz,height[i]) - tmp.begin() + 1;
            int rev_id = height.size()  - mpv + 1;
            int pos = read(rev_id);
            if(pos<i)  res = max(res,(i - pos) * height[i]);
            up(rev_id,i);
        }


        return res;
    }
};