Largest Rectangle in Histogram

Problem statement

A construction planner sees adjacent vertical columns, each one unit wide. The planner wants the largest rectangular panel that can fit entirely beneath their skyline without passing above any column in its chosen interval. Your task Find the maximum rectangle area in the histogram. A rectangle spans consecutive bars and its height cannot exceed the shortest bar in that interval. Important details Zero-height bars separate positive-height regions. A single bar may be optimal, and equal heights may span multiple positions. Use an O(n) monotonic-stack algorithm and a wide enough integer type for area. Worked example For heights [2, 4, 4, 1], the middle two bars support a rectangle of height 4 and width 2, area 8. No other interval gives a larger area.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the maximum area.

Constraints

1 <= n <= 100000; 0 <= heights <= 10000.

Sample input

4
2 4 4 1

Sample output

8