Largest Rectangle in Histogram

Given a histogram where each bar has a unit width and a provided height, your task is to compute the area of the largest rectangle that can be formed within the histogram. More formally, if the heights of the bars are given by (h_0, h_1, \dots, h_{n-1}), you need to find the maximum value of (h_j \times (i - j + 1)) over all contiguous ranges ([j, i]) such that all bars in the range have height at least (h_j).

inputFormat

The first line of input contains an integer (n) representing the number of bars in the histogram. The second line contains (n) space-separated integers representing the heights of the bars.

outputFormat

Output a single integer which is the area of the largest rectangle that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10