Largest Rectangle in Histogram

Given a histogram represented by a sequence of bars, the task is to find the largest rectangular area possible within the histogram. Each bar has a width of 1 and a height given by the input. The rectangle must be formed by consecutive bars and its area is given by the formula: $$\text{area} = \text{height} \times \text{width}$$ where the width is the number of consecutive bars.

For example, for the histogram with heights [2, 1, 5, 6, 2, 3], the largest rectangular area is 10.

inputFormat

The first line of input contains a single integer n representing the number of bars in the histogram. The second line contains n space-separated integers representing the heights of each bar.

For instance: 6\n2 1 5 6 2 3

outputFormat

Output a single integer that represents the largest rectangular area that can be formed in the histogram.

For the above example, the output should be 10.

6
2 1 5 6 2 3

10