package jjn.carl.monotonic_stack;
import java.util.Scanner;import java.util.Stack;
/** * @author Jiang Jining * @since 2023-08-27 10:25 */public class LeetCode84 {    public int largestRectangleArea(int[] heights) {        int[] newHeight = new int[heights.length + 2];        System.arraycopy(heights, 0, newHeight, 1, heights.length);        newHeight[heights.length+1] = 0;        newHeight[0] = 0;                Stack<Integer> stack = new Stack<>();        stack.push(0);                int res = 0;        for (int i = 1; i < newHeight.length; i++) {            while (newHeight[i] < newHeight[stack.peek()]) {                int mid = stack.pop();                int w = i - stack.peek() - 1;                int h = newHeight[mid];                res = Math.max(res, w * h);            }            stack.push(i);                    }        return res;    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] heights = new int[total];        for (int i = 0; i < total; i++) {            heights[i] = scanner.nextInt();        }        int largestRectangleArea = new LeetCode84().largestRectangleArea(heights);        System.out.println(largestRectangleArea);    }}