169. Largest Rectangle in a Histogram

Challenge1000 ms256 MBSolved by 0%

A histogram is n bars of width 1 standing side by side, each with a given height.

Find the area of the largest rectangle that fits entirely inside the histogram, and print it. The rectangle may span several bars, but its height is limited by the shortest bar it covers.

For heights [2, 1, 5, 6, 2, 3] the answer is 10 — the two bars of heights 5 and 6 give a rectangle 2 wide and 5 tall.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ height ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n space-separated integers.

Output

Print one integer — the area of the largest rectangle that fits inside the histogram.

Input6 2 1 5 6 2 3

Output10

Noteis the worked example from the statement

Input1 5

Output5

Noteis a single bar

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution