Largest Rectangle in a Histogram

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.

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.

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