# Function to find the largest rectangle area formed by given heights.
def largest_rectangle(heights):
    # Initialize a stack with a sentinel value -1.
    stack = [-1]

    # Initialize the variable to store the maximum area.
    max_area = 0

    # Iterate through the list of heights.
    for i in range(len(heights)):

        # Check if the current height is less than or equal to the height at the top of the stack.
        while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:

            # Pop the stack to get the height of the rectangle.
            current_height = heights[stack.pop()]

            # Calculate the right and left boundaries of the rectangle.
            right_boundary = i
            left_boundary = stack[-1]
            current_width = right_boundary - left_boundary - 1

            # Calculate the area of the current rectangle.
            current_area = current_height * current_width

            # Update the maximum area if the current area is greater.
            max_area = max(max_area, current_area)

        # Push the current index onto the stack.
        stack.append(i)

    # Calculate the length of the heights list.
    n = len(heights)

    # Process any remaining elements in the stack.
    while stack[-1] != -1:

        # Pop the stack to get the height of the rectangle.
        current_height = heights[stack.pop()]

        # Calculate the left boundary of the rectangle.
        left_boundary = stack[-1]
        current_width = n - stack[-1] - 1

        # Calculate the area of the current rectangle.
        current_area = current_height * current_width

        # Update the maximum area if the current area is greater.
        max_area = max(max_area, current_area)

    # Return the final maximum area of the largest rectangle.
    return max_area

# Driver code
def main():
    
    inputList = [
        [1, 3, 4, 2, 2],
        [2, 1, 5, 6, 2, 3],
        [2, 4, 5, 7, 3, 9],
        [1, 2, 3, 4, 5],
        [3, 1, 3, 4, 2, 1, 5, 4, 2, 3, 1, 2, 3, 2, 4, 1, 2, 2, 5, 3],
        [1, 2, 3, 2, 5, 6, 2, 1, 4, 3, 2, 3, 4, 1, 3, 2, 3, 4, 5, 1]
    ]
    
    for i in range(len(inputList)):
        print (str(i + 1) + '.\tHeights:', inputList[i])
        print ('\tArea of the largest rectangle:', largest_rectangle(inputList[i]))
        print ('-' * 100)

if __name__ == '__main__':
    main()