1440. Largest Rectangle in a Histogram

#include <iostream>
#include <stack>

using namespace std;
using ll = long long;

struct rec {
    ll high, width;
};

int main() {
    int n;
    while (scanf("%d", &n) && n != 0) {
        stack<rec> sta;
        ll ans{};
        rec fir{ 0,1 };
        sta.push(fir);
        ll h;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &h);
            rec mid{ h,1 };
            if (mid.high > sta.top().high) sta.push(mid);
            else {
                ll wid{};
                while (mid.high < sta.top().high) {
                    wid += sta.top().width;
                    ans = max(ans, ll(wid * sta.top().high));
                    sta.pop();
                }
                rec m{ h, wid + 1 };
                sta.push(m);
            }
        }
        rec last{ 0,1 };
        ll wid{};
        while (last.high < sta.top().high) {
            wid += sta.top().width;
            ans = max(ans, ll(wid * sta.top().high));
            sta.pop();
        }
        printf("%lld\n", ans);
    }
}