The mayor of a certain city wants to give the buildings a fresh coat of paint.
The city has n buildings of equal widths but different heights, there is no space between each building.
Being a cheapskate, the mayor decides that only a SINGLE large rectangular block will be painted across the buildings.
Your task is to find the area of the largest such rectangular block that can be painted.
NOTE: Not all buildings must be painted across.
The input will begin with a single integer n (1 ≤ n ≤ 1,000,000), which is the number of buildings.
The following line will have n integers, giving the heights of the buildings from left to right.
You are to output the area of the largest rectangular block that can be painted. The area of the block will always fit in a 32-bit integer.
For 30% of the test cases, n
Sample Input 1
1 2 2 3 2 1 2
Sample Output 1
Explanation for Sample Output 1
In the above cityscape, the maximum area is 4*2=8 rectangular units, as shaded in red below: