Largest Rectangle in Histogram

Given n non-negative integers representing the heights of histogram bars where the width of each bar is 1, your task is to find the area of the largest rectangle that can be formed within the bounds of the histogram.

Mathematically, if the histogram is represented as an array \(H = [h_1, h_2, \dots, h_n]\), then for any contiguous segment \(H[i \dots j]\), the area of the rectangle using the minimum height within that range is given by:

\( \text{Area} = \min_{i \le k \le j}h_k \times (j - i + 1) \).

Your task is to compute the maximum such rectangle area.

inputFormat

The first line of input contains a single integer n (\(0 \leq n \leq 10^5\)) which represents the number of bars in the histogram. If n is greater than 0, the second line contains n space-separated non-negative integers representing the bar heights.

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

</p>