Maximum Rectangular Area in a Histogram

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit, there will be N bars height of each bar will be given by the array arr.

Input Format

The first line contains an integer n the length of the original array a, n denoting the height of each bar. The second line contains n integers a1, a2, … the array elements themselves.

Output Format

Print the largest rectangular area possible.

Example 1:

Input:
    7
    6 2 5 4 5 1 6
Output:
    12

Example 2:

Input:
    8
    7 2 8 9 1 3 6 5
Output:
    16
Explanation:
    Maximum size of the histogram
    will be 8  and there will be 2 consecutive
    histogram. And hence the area of the
    histogram will be 8x2 = 16.

Constraints:

• 1 ≤ N ≤ 1000000
• 1 ≤ arr[i] ≤ 1000000000000
• Expected Time Complexity: O(N)
• Expected Auxiliary Space: O(N)