Largest Area Histogram

hard

1. You are given a number n, representing the size of array a.
2. You are given n numbers, representing the height of bars in a bar chart.
3. You are required to find and print the area of largest rectangle in the histogram.

e.g.
for the array [6 2 5 4 5 1 6] -&gt; 12

Input Format

Input is managed for you

Output Format

A number representing area of largest rectangle in histogram

Constraints

0 &lt;= n &lt; 20
0 &lt;= a[i] &lt;= 10

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

Balanced Brackets

Infix Evaluation