Description

Given n non-negative integers representingthe histogram's bar height

where the width of each bar is 1, find thearea of largest rectangle in the histogram.

Above is a histogram where width of eachbar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in theshaded area, which has area = 10 unit.

Input Format

每组数据分两行，第一行一个N，表示数组长度

第二行N个数字，表示N个矩形的高度

Output Format

根据题意输出

Sample

6
2 1 5 6 2 3

10