Largest Rectangle in a Histogram

Interview

Time limit1sMemory limit256 MB

Summary

Given a histogram of unit-width bars with varying heights, find the area of the largest rectangle that fits inside it, processing several test cases until a 0 terminates input.

Level: Medium6 of 10
Topics: Stack, Array, Greedy, Implementation
Solved: No attempts yet

Problem

A histogram is a shape made of several rectangles standing side by side on a common baseline. Every rectangle has the same width of $1$ , but the heights may differ. For example, seven rectangles with heights $2, 1, 4, 5, 1, 3, 3$ placed next to each other from left to right form one histogram.

Write a program that finds the area of the largest rectangle that fits entirely inside the given histogram. Such a rectangle spans some number of consecutive bars, and its height equals the smallest height among the bars it covers.

Input

The input consists of several test cases. Each test case is given on a single line. First comes the number of rectangles $n$ ( $1 \le n \le 100{,}000$ ), followed by the heights $h_1, h_2, \ldots, h_n$ of the rectangles in left-to-right order ( $0 \le h_i \le 1{,}000{,}000{,}000$ ). Every rectangle has width $1$ .

The last line contains a single $0$ and must not be processed.

Output

For each test case, print on its own line the area of the largest rectangle in the histogram.

Examples3

Example 1

Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Expected output

8
4000

Example 2
Input
```
1 5
0
```
Expected output
```
5
```
Example 3
Input
```
3 1 2 3
2 4 4
0
```
Expected output
```
4
8
```