|Contests||Virtual Contests||Problems||Submit||Runs Status||Rank List||Forum|
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 ≤ n ≤ 100000. Then follow n integers h1,...,hn, where 0 ≤ hi ≤ 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000