Description
We are given a bar graph consisting of adjacent bars.
Each bar starts from height 0, has width 1, and the ith bar has height Hi.
The task is to find the area of the largest rectangle that can fit entirely inside this bar graph.
More formally, find:
.
For sample input 1, this is the maximum rectangular area.
For sample input 2, there are two cases of maximum rectangular area.
Subtasks:
Testcases 1, 2: N <= 100.
Testcases 3, 4: N <= 1919.
Testcases 5, 6: no further constraints.
Input
The first line contains one integer N, the number of bars.
The second line contains N integers, where the ith one represents the height of the ith bar(Hi).
It is guaranteed that:
Output
Output a single integer — the maximum rectangular area inside the bar graph.
(Print a newline after the output.)