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

    max_area = 0

    for i in range(len(heights)):

        while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:

            current_height = heights[stack.pop()]

            right_boundary = i
            left_boundary = stack[-1]
            current_width = right_boundary - left_boundary - 1

            current_area = current_height * current_width

            max_area = max(max_area, current_area)

        stack.append(i)

    n = len(heights)

    while stack[-1] != -1:

        current_height = heights[stack.pop()]

        left_boundary = stack[-1]
        current_width = n - stack[-1] - 1

        current_area = current_height * current_width

        max_area = max(max_area, current_area)

    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()