Given an array of integers heights representing the height of bars in a histogram, find the largest rectangle that can fit inside the histogram.

Parameter

heights: A list of integer representing the height of each bar in the histogram. Each bar has a width of 1.

Result

The area of the largest rectangle that can fit inside the histogram.

Example

Example 1

Input: heights = [3, 5, 6, 2, 1, 4]

Output: 10