Maximum Histogram Area

Given n histogram bars with unit width and varying heights, find the largest rectangular area that can be formed in the histogram. The rectangle's area is computed as the height of the bar multiplied by the number of consecutive bars that have heights no less than that bar. Mathematically, the area for a particular bar is given by ( \text{area}_i = h_i \times (\text{right}_i - \text{left}_i - 1) ), where (h_i) is the height of the bar, and (\text{left}_i) and (\text{right}_i) are the indices of the next smaller bars on the left and right of i respectively.

inputFormat

The first line contains an integer n representing the number of histogram bars. The second line contains n space-separated integers that represent the heights of the histogram bars.

outputFormat

Output a single integer representing the maximum rectangular area that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10