long largestRectangle(int n, const vector<long>& H) {
    vector<int> prevSmaller(n, -1), nextSmaller(n, n);
    stack<int> prev, next;
    prev.push(0);
    next.push(n-1);
    for (int i = n-2; i >= 0; i--) {
        while (!next.empty() and H[i] <= H[next.top()]) next.pop();
        if (!next.empty()) nextSmaller[i] = next.top();
        next.push(i);
    }
    long maxArea = H[0] * nextSmaller[0];
    for (int i = 1; i < n; i++) {
        while (!prev.empty() and H[i] <= H[prev.top()]) prev.pop();
        if (!prev.empty()) prevSmaller[i] = prev.top();
        prev.push(i);
        maxArea = max(maxArea, H[i] * (nextSmaller[i] - prevSmaller[i] - 1));
    }
    return maxArea;
}