Largest Area

May 10

Given N non-negative integers representing the histogram's bar height where the width of each bar is 1. Find the area of the largest rectangle in the histogram.

Solve this Question



Given N non-negative integers representing the histogram's bar height where the width of each bar is 1. Find the area of the largest rectangle in the histogram.

Input Format

  • Given a number N denoting the number of bars.
  • The second line will contain N space-separated numbers denoting the height of all bars.

Constraints

  • 1 <= N <= 107
  • 1 <= height <= 107

Output Format

  • Print the area of the largest rectangle.

Sample Input

4
10 20 8 12

Sample Output

32


Solution to this question is not available right now.