class Result {

    // SIMPLEST & BEST APPROACH
    // Largest Rectangle using Linear Iteration, with Stack
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n) | AC: O(n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Explicit Stack Depth

    public static long solveSimpleIterativeWithStack(List<Integer> h) {
        int n = h.size();

        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;

        for (int i = 0; i <= n; i++) {
            long curHeight = ((i == n) ? 0 : h.get(i));
            while (!stack.isEmpty() && curHeight < h.get(stack.peek())) {
                int height = h.get(stack.pop());
                int width = (stack.isEmpty() ? i : (i - stack.peek() - 1));
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }


    // Largest Rectangle using Divide & Conquer (Recursive) Approach
    //      No Stacks used in this Solution.
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n^2) | AC: O(n * log n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Recursion Depth
    private static long solveDivNCnqRecursive(List<Integer> h, int start, int end) {
        if (start > end) {
            return 0;
        }

        // Find index of minimum height in current range
        int minIndex = start;
        for (int i = (start + 1); i <= end; i++) {
            if (h.get(i) < h.get(minIndex)) {
                minIndex = i;
            }
        }

        // Area using the minimum height across entire range
        long areaWithMin = (long) (h.get(minIndex) * (end - start + 1));

        // Recurse on left and right sublists
        long leftArea = solveDivNCnqRecursive(h, start, minIndex - 1);
        long rightArea = solveDivNCnqRecursive(h, minIndex + 1, end);

        return Math.max(areaWithMin, Math.max(leftArea, rightArea));
    }


    // Largest Rectangle using Divide & Conquer (Non-Recursive / Iterative) Approach
    //      Stack is used to simulate Recursion
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n^2) | AC: O(n * log n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Explicit Stack Depth
    public static long solveDivNCnqIterative(List<Integer> h) {
        long maxArea = 0;

        Stack<int[]> stack = new Stack<>(); // each element: [start, end]
        stack.push(new int[]{0, h.size() - 1});

        while (!stack.isEmpty()) {
            int[] range = stack.pop();
            int start = range[0], end = range[1];
            if (start > end) continue;

            // Find min index in current range
            int minIndex = start;
            for (int i = start + 1; i <= end; i++) {
                if (h.get(i) < h.get(minIndex)) {
                    minIndex = i;
                }
            }

            // Compute area with this min height
            long areaWithMin = (long) h.get(minIndex) * (end - start + 1);
            maxArea = Math.max(maxArea, areaWithMin);

            // Push left and right ranges
            stack.push(new int[]{start, minIndex - 1});
            stack.push(new int[]{minIndex + 1, end});
        }

        return maxArea;
    }

    /*
     * Complete the 'largestRectangle' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts INTEGER_ARRAY h as parameter.
     */

    public static long largestRectangle(List<Integer> h) {
        // Write your code here
        return solveSimpleIterativeWithStack(h);
        // return solveDivNCnqRecursive(h, 0, h.size() - 1);
        // return solveDivNCnqIterative(h);
    }

}